问题描述
Peter有一个序列$a_1, a_2, ..., a_n$. 定义$g(l,r)$表示子序列$a_{l},a_{l+1},...,a_{r}$的最大值, $f(l,r)=\displaystyle\sum_{i=l}^{r}[a_i = g(l,r)]$. 注意$[\text{condition}] = 1$当且仅当$\text{condition}$是true, 否则$[\text{condition}] = 0$.
对于每个整数$k \in \{1, 2, ..., n\}$, Peter想要知道有多少整数对$l$和$r$ $(l \le r)$满足$f(l,r)=k$.
输入描述
输入包含多组数据, 第一行包含一个整数$T$表示测试数据组数. 对于每组数据:
第一行包含一个整数$n$ $(1 \le n \le 60000)$表示序列的长度. 第二行包含$n$个整数$a_1,a_2,...,a_n$ $(1 \le a_i \le n)$.
输出描述
对于每组数据, 输出一个整数$S = \displaystyle\sum_{k=1}^{n}k \oplus z_k$, 其中$z_k$表示满足$f(l,r)=k$的数对$l$和$r$的个数, $\oplus$是异或位运算操作.
输入样例
3
3
1 2 3
4
1 1 1 1
6
1 2 2 1 1 2
输出样例
12
12
36
