시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 (추가 시간 없음) | 256 MB | 22 | 5 | 4 | 25.000% |
Chiaki has an array of integers $a_1,a_2,\dots, a_n$. Chaiki can replace an element $a_x$ to another integer $y$. Let the resulting array be $b_1,b_2,\dots,b_n$, Chiaki would like to know the minimum value of $|a_x-y| + \sum\limits_{k=1}^{n} k \cdot c_k$, where $c_k$ is the number of distinct integers in $b_1,b_2,\dots,b_k$.
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $n$ ($1 \le n \le 10^6$) -- the length of the array.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).
It is guaranteed that the sum of $n$ in all test cases will not exceed $10^6$.
For each test case, output an integer denoting the answer.
1 4 1 2 3 4
22