题目描述

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

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

具体来说，一座山可以描述为一条折线，折线的下方是岩石。这条折线有 $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$ 。