U503856 走地鸡群

>踏上旅途之后，SCUTkk 和你一起到达不同的带砖，挑战当地的馆主，并收服了许多的走地鸡，SCUT 散养走地鸡大军初具规模。

然而在挑战空间系道馆馆主 hei_yu_bai 的战斗中，以 SCUTkk 为首的走地鸡群不幸地被二向箔袭击了，所幸由于走地鸡强大的生命力，你们只是变成了平面生物而没有受到其他伤害。 某一天，走地鸡所在的世界里下起了暴雨。初始时（**零时刻**）水面高度为 $0$，然后雨水在地面堆积，水面开始以**每分钟一单位长度**的速度上涨。如果某一时刻，水面的高度**大于等于**某个坐标位置处的地面高度，那么上升的水面会将该处的地面**淹没**）。 显然，走地鸡是**无法生活**在被水淹没的区域，也**无法跨越水面**的。随着水面的上涨，它们只能不断地向**更高**的位置走去以躲避积水。 我们规定：**无需跨越水面**就能到达彼此位置的两只走地鸡属于同一个鸡群，否则属于不同鸡群。并且，由于走地鸡的数量足够多，保证任何时候，每一个还**未被淹没**的位置处**都存在**走地鸡。 如果所有地面都被淹没，那么鸡群的数量将会**变成零**！作为走地鸡的首领，SCUTkk 当然不想看到这种情况，所以他迫切地想要知道：从初始时刻到全部地面都被淹没为止，在**每一分钟**时刻，走地鸡会被划分为多少个不同的鸡群。但由于它只是一只走地鸡，不会这种高难度问题，因此它只能请你帮忙。 **形式化的说：** 在初始时刻，水面高度 $h = 0$, 地面的坐标为 $1 \sim n$ 。 有一个长度为 $n(n \ge 3)$ 的数组 $a$，其中 $a_i$ 表示坐标为 $i$ 处的地面的高度。保证数组 $a$ 满足 $a_1 = 0, a_n = 0$，且对所有的 $2 \le i \le n - 1$，有 $a_i \ge 0$。 在第 $k$ 分钟时，水面高度 $h = k$，请求出此时存在多少个不同的二元组 $(x, y)$，满足 $a_x \le h, a_y \le h$, 并且对所有的 $x < i < y$，有 $a_i > h$。 **注意：**二元组 $(x, y)$ 应满足 $1 \le x \le n$，$1 \le y \le n$，且 $y - x \ge 2$ 。 设 $d = \max \limits_{1 < i < n} a_i$，你需要对所有的 $0 \le k \le d$ 都求出 $h = k$ 时合法的二元组 $(x, y)$ 的数量。

第一行一个正整数 $n$ $(3 \le n \le 2 \times 10^5)$，表示数组 $a$ 的长度。 第二行 $n$ 个整数 $a_i$ $(0 \le a_i \le 10^6)$, 其中 $a_i$ 表示坐标为 $i$ 处的地面的高度。

为了简化输出，你只需要输出一行**一个整数** $ans = \oplus _{k} ans_k$（$0 \le k \le \max \limits_{1 < i < n} a_i$），即所有时刻答案的**异或和**，具体可看样例解释。 **异或：** 即两个数的二进制按位异或运算。$a \oplus b$ 指的是：对于每一个二进制位，若 $a$ 和 $b$ 的二进制表示在这一位上都为 $0$ 或都为 $1$，那么 $a \oplus b$ 的结果在这一位上为 $0$，否则结果在这一位上为 $1$。 **异或和：** 多个数的按位异或和的计算方式如下：$a \oplus b \oplus c \oplus d = ((( a \oplus b ) \oplus c) \oplus d)$。另外，按位异或运算满足交换律和结合律。 **注意：** 在程序语言中，$a \oplus b$ 写作 **$a$ ^ $b$**。

第一个样例中，$ans_0 = 1,ans_1 = 1, ans_2 = 1, ans_3 = 0,$ 则 $ans = 1 \oplus1\oplus1\oplus0 = 1$。 第二个样例中，$ans_0 = 1, ans_1 = 2, ans_2 = 1, ans_3 = 0$, 则 $ans = 1 \oplus2\oplus1\oplus0 = 2$。