Eades

Peter has a number sequence $a_1, a_2, ..., a_n$. Let $g(l,r)$ be the maximum value of the subsequence $a_{l},a_{l+1},...,a_{r}$ and $f(l,r)=\displaystyle\sum_{i=l}^{r}[a_i = g(l,r)]$. Note that $[\text{condition}] = 1$ if $\text{condition}$ is true, or $0$ otherwise.

Peter wants to know the number of integer pairs $l$ and $r$ $(l \le r)$ such that $f(l,r)=k$, for every integer $k \in \{1, 2, ..., n\}$.

There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:

The first contains an integer $n$ $(1 \le n \le 60000)$ -- the length of the sequence. The second line contains $n$ integers $a_1,a_2,...,a_n$ $(1 \le a_i \le n)$.

For each test case, output an integer $S = \displaystyle\sum_{k=1}^{n}k \oplus z_k$, where $z_k$ is the number of integer pairs $l$ and $r$ $(l \le r)$ that $f(l,r)=k$ and $\oplus$ denotes the bitwise exclusive or operation.

3
3
1 2 3
4
1 1 1 1
6
1 2 2 1 1 2

12
12
36

BestCoder Round #84