Kujou Karen is a girl who loves sports.

One day, she went mountain climbing. To ensure her safety, her father hired several bodyguards and stationed them at fixed positions on the mountain to monitor Karen in real-time.

Specifically, the mountain can be described as a polyline, with rock beneath it. This polyline has $n$ vertices, and there is a pavilion at each vertex. The coordinates of the $i$-th vertex are $(i, h_i)$. Karen will only play at the pavilions, and the bodyguards will only monitor her from the pavilions.

Due to technical reasons, a bodyguard can only monitor all pavilions that they can see, provided the pavilion's x-coordinate does not exceed the bodyguard's own x-coordinate. We say a bodyguard at pavilion $q$ can see a pavilion $p$ if and only if the line segment connecting $q$ and $p$ does not pass through any rock. Specifically, if this line segment passes through any pavilion other than $p$ and $q$, we consider the bodyguard unable to see Karen at $p$.

Hiring bodyguards is expensive, and Karen's father wants to minimize the number of bodyguards.

Karen's father also wants a detailed hiring plan. He knows that some pavilions might be under maintenance, and he wants to calculate for all $1 \leq l \leq r \leq n$: if it is known in advance that only the pavilions in the interval $[l, r]$ can be used for playing (and monitoring), what is the minimum number of bodyguards required to ensure that every pavilion in $[l, r]$ is monitored?

Karen's father has already obtained a result and wants you to verify if his result is correct.

Input

The first line contains an integer $n$, representing the number of pavilions.

The next line contains $n$ integers, where the $i$-th integer $h_i$ represents the coordinates of the $i$-th pavilion as $(i, h_i)$.

Output

Calculate for all $1 \leq l \leq r \leq n$: if it is known in advance that Karen will only play at pavilions in the interval $[l, r]$, what is the minimum number of bodyguards required to ensure that every pavilion in $[l, r]$ is monitored? Since the output volume is too large, Karen's father only requires you to output the XOR sum of the answers for all $[l, r]$.

Examples

Input 1

3
2 3 1

Output 1

3

Note 1

If $r - l + 1 \leq 2$, the answer is clearly $1$.

If $l = 1, r = n$, the answer is $2$; two bodyguards need to be stationed at $(2, 3)$ and $(3, 1)$ to monitor Karen.

Input 2

20
1000000000 9 333333333 1 200000000 7 142857142 9 111111111 1 57753574 794671546 843856123 707837667 715731730 40241035 459666790 914023043 827718482 858423480

Output 2

3

Subtasks

For $30\%$ of the data, $n \leq 20$.

For $70\%$ of the data, $n \leq 500$.

For $100\%$ of the data, $n \leq 5000$.

For $100\%$ of the data, $1 \leq h_i \leq 10^9$.