#2545. 「JXOI2018」守卫

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

九条可怜是一个热爱运动的女孩子。

这一天她去爬山,她的父亲为了她的安全,雇了一些保镖,让他们固定地呆在在山的某些位置,来实时监视九条可怜,从而保护她。

具体来说,一座山可以描述为一条折线,折线的下方是岩石。这条折线有 n 个折点,每个折点上有一个亭子,第 i 个折点的坐标是 (i,h_i) 九条可怜只可能会在亭子处玩耍,那些保镖也只会在亭子处监视可怜。

由于技术方面的原因,一个保镖只能监视所有他能看得到的,横坐标不超过他所在位置的亭子。我们称一个保镖能看到一个亭子 p ,当且仅当他所在的亭子 q p 的连线不经过任何一块岩石。特别地,如果这条连线恰好经过了除了 p,q 以外的亭子,那么我们认为保镖看不到可怜。

雇佣保镖是一件很费钱的事情,可怜的父亲希望保镖越少越好。

可怜的父亲还希望得到详尽的雇佣保镖的方案,他知道有些亭子可能正在维修,他想对所有的 1\leq l\leq r\leq n 计算:如果事先已知了只有区间 [l,r] 的亭子可以用来玩耍(和监视),那么最少需要多少个保镖,才能让 [l,r] 中的每一个亭子都被监视到。

可怜的父亲已经得到了一个结果,他希望和你核实他的结果是否正确。

输入格式

第一行输入一个整数 n 表示亭子的数目。 接下来一行 n 个整数,第 i 个整数 h_i 表示第 i 个亭子的坐标是 (i,h_i)

输出格式

对所有的 1\leq l\leq r\leq n 计算:如果事先已知了可怜只会在 [l,r] 这个区间的亭子里面玩耍,那么最少需要多少个保镖,才能让 [l,r] 中的每一个亭子都被监视到。由于输出量太大,可怜的父亲只要你输出所有 [l,r] 的答案的异或即可。

样例

样例输入

3
2 3 1

样例输出

3

样例解释

如果 r-l+1\leq 2 ,那么答案显然是 1 。 如果 l=1,r=n ,那么答案是 2 ,需要安排两个保镖在 (2,3),(3,1) 两个位置监视可怜。

数据范围与提示

对于 30\% 的数据, n\leq 20
对于 70\% 的数据, n\leq 500
对于 100\% 的数据, n\leq 5000
对于 100\% 的数据, 1\leq h_i\leq 10^9