CF2101C.23 Kingdom

我们定义 $d_x(c)$ 为整数 $x$ 在数列 $c$ 中的距离，也就是 $c$ 中出现的两个 $x$ 之间的最长间隔。若 $x$ 出现的次数不足两次则为零。

形式化地，$d_x(c)=\max\limits_{1\le i<j\le\vert c\vert\wedge c_i=c_j=x}(j-i)$。

定义一个数列 $c$ 的美丽度为 $\sum\limits_{i=1}^n d_i(c)$。

给你一个长为 $n$ 的数列 $a$，你将构造一个长为 $n$ 的数列 $b$，要求每一项均满足 $1\le b_i\le a_i$。求这样的 $b$ 的最大美丽度。你需要求出这个值。

多组数据，第一行一个整数 $t(1\le t\le 10^4)$ 表示数据组数。

对于每组数据：
第一行一个整数 $n(1\le n\le 2\times 10^5)$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\le a_i\le n)$。

保证单个测试点中 $\sum n\le 2\times 10^5$。

每组数据输出一行一个整数，表示答案。

样例解释

第一组数据中，令 $b=(1,2,1,2)$，$d_1(b)=3-1=2,d_2(b)=4-2=2$，美丽度为 $4$。可以证明这个可能的最大的美丽值。

第二组数据中，令 $b=(1,1)$ 或 $b=(2,2)$ 均可得到 $1$ 的美丽值。

第三组数据中，令 $b=(1,2,1,4,1,2,1,1,1,2)$，则有 $d_1(b)=9-1=8,d_2(b)=10-2=8,d_4(b)=0$，可以获得 $16$ 的美丽值。

By @chenxi2009