C. 23 王国

每个测试的时间限制： $4$ 秒
内存限制： $256$ 兆字节

---

题目描述

对于数组 $c$ 中的某个值 $x$，其距离 $d_x(c)$ 定义为 $x$ 在 $c$ 中任意两次出现之间的最大间隔。

形式化地说，
设所有满足 $i < j$ 且 $c_i = c_j = x$ 的数对 $(i, j)$，定义
[ d_x(c) = \max (j - i) ]
如果 $x$ 在 $c$ 中只出现一次或未出现，则 $d_x(c) = 0$。

一个数组的美丽值定义为数组中每个不同值的距离之和。
形式化地说，数组 $c$ 的美丽值为： [ \sum_{1 \le x \le n} d_x(c) ]

---

给定一个长度为 $n$ 的数组 $a$。
一个数组 $b$ 被称为nice，如果它也满足：

• 长度为 $n$
• 对于所有 $1 \le i \le n$，有 $1 \le b_i \le a_i$

你的任务是：在所有可能的 nice 数组 $b$ 中，找出最大可能的美丽值。

---

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

接下来每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）—— 数组 $a$ 的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。

数据保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

---

输出格式

对于每个测试用例，输出一个整数，表示所有 nice 数组 $b$ 中最大可能的美值。

---

示例

输入

4
4
1 2 1 2
2
2 2
10
1 2 1 5 1 2 2 1 1 2
8
1 5 2 8 4 1 4 2

输出

4
1
16
16

---

样例解释

第一个测试用例

如果取 $b = [1, 2, 1, 2]$，
则 $d_1(b) = 3 - 1 = 2$，$d_2(b) = 4 - 2 = 2$，
美丽值为 $2 + 2 = 4$。可以证明没有比 $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$，
美丽值为 $8 + 8 = 16$。