CF2248C.Maximize the Score

You are given an array $a$ of length $2n$. Each integer from $1$ to $n$ occurs exactly twice in $a$.

Initially, your score is $0$.

You can repeatedly perform the following operation while $a$ is non-empty:

• Choose an integer $x$ that is present in $a$.
• Let $l$ and $r$ be the indices of the leftmost and rightmost occurrences of $x$ in the current array, respectively. If $x$ occurs only once, then $l = r$.
• Add $(r - l + 1)^2$ to your score.
• Delete the elements $a_l, a_{l + 1}, \ldots, a_r$ from $a$. The remaining elements are concatenated without changing their order and re-indexed starting from $1$.

Find the maximum possible score after making the array empty.

给你一个长度为 $2n$ 的数组 $a$。其中，从 $1$ 到 $n$ 的每个整数在 $a$ 中恰好出现两次。

初始时，你的得分为 $0$。

当数组 $a$ 非空时，你可以重复执行以下操作：

• 选择一个当前存在于 $a$ 中的整数 $x$；
• 设 $l$ 和 $r$ 分别为 $x$ 在当前数组中最左侧和最右侧出现位置的下标（若 $x$ 仅出现一次，则 $l = r$）；
• 将 $(r - l + 1)^2$ 加入你的得分；
• 从 $a$ 中删除元素 $a_l, a_{l + 1}, \ldots, a_r$；剩余元素保持原有顺序拼接，并重新从下标 $1$ 开始编号。

求将数组清空后所能获得的最大可能得分。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ($1 \le a_i \le n$).

It is guaranteed that each integer from $1$ to $n$ occurs exactly twice in $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

第二行包含 $2n$ 个整数 $a_1, a_2, \ldots, a_{2n}$（$1 \le a_i \le n$）。

保证 $a$ 中恰好包含 $1$ 到 $n$ 的每个整数各两次。

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

For each test case, output a single integer — the maximum possible score.

对于每个测试用例，输出一个整数——可能获得的最高分数。

In the second test case, one optimal strategy is to choose $x = 1$ first. This deletes the subarray $[1, 2, 1]$ and adds $3^2 = 9$ to the score. The remaining array is $[2]$; choosing $x = 2$ adds $1$. The total score is $10$.

In the third test case, choosing $x = 1$ deletes the whole array and adds $4^2 = 16$ to the score.

In the fourth test case, choose $x = 1$ first and then choose $x = 2$. The total score is $2^2 + 4^2 = 20$.

In the sixth test case, choose $x = 2$ first. This deletes the subarray $[2, 3, 4, 1, 2]$ from the middle of the array and adds $5^2 = 25$ to the score. After deleting this subarray and concatenating the remaining elements, the array becomes $[1, 3, 4]$. Choosing each of the three remaining values then adds $1$, so the total score is $28$.

在第二个测试用例中，一种最优策略是首先选择 $x = 1$。这将删除子数组 $[1, 2, 1]$，并向得分中添加 $3^2 = 9$。剩余数组为 $[2]$；再选择 $x = 2$ 可额外获得 $1$ 分。总得分为 $10$。

在第三个测试用例中，选择 $x = 1$ 将删除整个数组，并向得分中添加 $4^2 = 16$。

在第四个测试用例中，先选择 $x = 1$，再选择 $x = 2$。总得分为 $2^2 + 4^2 = 20$。

在第六个测试用例中，首先选择 $x = 2$。这将从数组中间删除子数组 $[2, 3, 4, 1, 2]$，并向得分中添加 $5^2 = 25$。删除该子数组并将剩余元素拼接后，数组变为 $[1, 3, 4]$。随后对剩余的三个值分别进行选择，各得 $1$ 分，因此总得分为 $28$。