CF2248C Maximize the Score

给定一个长度为 $2n$ 的数组 $a$。每个整数 $1$ 到 $n$ 在 $a$ 中恰好出现两次。 初始分数为 $0$。 你可以重复执行以下操作，直到 $a$ 为空： - 选择一个当前在 $a$ 中出现的整数 $x$。 - 设 $l$ 和 $r$ 为当前数组中 $x$ 最左和最右出现位置的下标。如果 $x$ 只出现一次，则 $l = r$。 - 将 $(r - l + 1)^2$ 加到分数中。 - 删除子数组 $a_l, a_{l + 1}, \ldots, a_r$。剩余元素按原顺序重新拼接成一个新数组，并重新编号下标从 $1$ 开始。 请你求出将数组删空后，最大可能获得的分数。

每个测试点包含多组测试数据。第一行是测试用例数 $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$）。 保证每个 $1$ 到 $n$ 的整数在 $a$ 中恰好出现两次。 保证所有测试用例中 $n$ 之和不超过 $2 \times 10^5$。

对于每个测试用例，输出一行一个整数，表示可以获得的最大分数。

在第二个样例中，一种最优方案是首先选择 $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$。 由 ChatGPT 5 翻译