[JXOI2018]守卫

题目背景

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

题目描述

这一天她去爬山,她的父亲为了她的安全,雇了一些保镖,让他们固定地呆在在山的某些位置,来实时监视九条可怜,从而保护她。 具体来说,一座山可以描述为一条折线,折线的下方是岩石。这条折线有 $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]$的答案的异或即可。

输入输出样例

输入样例 #1

3
2 3 1

输出样例 #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$, $1\leq h_i\leq 10^9$ 。