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.

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 $ .

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 $ .