Maximize the ScoreAI (CI翻译)
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.
Input
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$.
Output
For each test case, output a single integer — the maximum possible score.
Note
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$.
{"titleZh":"最大化得分","bodyZh":"你有一个长度为 $2n$ 的数组 $a$。$1$ 到 $n$ 的每个整数在 $a$ 中恰好出现两次。\n\n初始时，你的得分为 $0$。\n\n当 $a$ 非空时，你可以反复进行以下操作：\n\n- 选择一个当前存在于 $a$ 中的整数 $x$。\n- 令 $l$ 和 $r$ 分别为当前数组中 $x$ 的最左和最右出现位置。如果 $x$ 只出现一次，则 $l = r$。\n- 将 $(r - l + 1)^2$ 加入得分。\n- 从 $a$ 中删除元素 $a_l, a_{l + 1}, \ldots, a_r$。剩余元素在不改变顺序的情况下连接起来，并从 $1$ 开始重新编号。\n\n求将数组清空后可能获得的最大得分。\n\n## 输入格式\n\n每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是各测试用例的描述。\n\n每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。\n\n第二行包含 $2n$ 个整数 $a_1, a_2, \ldots, a_{2n}$（$1 \le a_i \le n$）。\n\n保证 $1$ 到 $n$ 的每个整数在 $a$ 中恰好出现两次。\n\n保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。\n\n## 输出格式\n\n对于每个测试用例，输出一个整数——可能获得的最大得分。\n\n## 说明\n\n在第二个测试用例中，一种最优策略是首先选择 $x = 1$。这会删除子数组 $[1, 2, 1]$，并将 $3^2 = 9$ 加入得分。剩余数组为 $[2]；选择 $x = 2$ 后得分增加 $1$。总得分为 $10$。\n\n在第三个测试用例中，选择 $x = 1$ 会删除整个数组，并将 $4^2 = 16$ 加入得分。\n\n在第四个测试用例中，首先选择 $x = 1$，然后选择 $x = 2$。总得分为 $2^2 + 4^2 = 20$。\n\n在第六个测试用例中，首先选择 $x = 2$。这会删除数组中间的子数组 $[2, 3, 4, 1, 2]$，并将 $5^2 = 25$ 加入得分。删除该子数组并连接剩余元素后，数组变为 $[1, 3, 4]$。随后选择剩余的三个值，每次得分增加 $1$，因此总得分为 $28$。"}AI (CI翻译)
样例
6
1
1 1
2
1 2 1 2
2
1 2 2 1
3
1 1 2 3 3 2
3
1 2 3 3 2 1
4
1 2 3 4 1 2 3 4
4
10
16
20
36
28
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。