Array

시간 제한5초메모리 제한256 MB

요약

한 원소를 임의의 정수 y로 바꾸며 |a_x - y|를 지불할 때, 접두사별 서로 다른 값 개수의 가중합과 교체 비용의 합을 최소로 만든다.

난이도: 어려움10점 중 8점
유형: 배열, 해시맵, 누적 합, 그리디
정답자: 아직 제출이 없습니다

문제

Chiaki는 정수 배열 $a_1,a_2,\dots,a_n$ 을 가지고 있다. Chiaki는 원소 $a_x$ 를 다른 정수 $y$ 로 바꿀 수 있다. 바뀐 배열을 $b_1,b_2,\dots,b_n$ 이라 할 때, Chiaki는 $|a_x-y| + \sum_{k=1}^{n} k \cdot c_k$ 의 최솟값을 알고 싶어 한다. 여기서 $c_k$ 는 $b_1,b_2,\dots,b_k$ 에 등장하는 서로 다른 정수의 개수이다.

입력

여러 개의 테스트 케이스가 주어진다. 입력의 첫째 줄에는 테스트 케이스의 수 $T$ 가 주어진다. 각 테스트 케이스는 다음과 같다.

첫째 줄에는 배열의 길이 $n$ 이 주어진다 ( $1 \le n \le 10^6$ ).

둘째 줄에는 $n$ 개의 정수 $a_1, a_2, \dots, a_n$ 이 주어진다 ( $1 \le a_i \le 10^9$ ).

모든 테스트 케이스에서 $n$ 의 합은 $10^6$ 을 넘지 않는다.

출력

각 테스트 케이스마다 답을 나타내는 정수를 한 줄에 출력한다.

예제1

예제 1
입력
```
1
4
1 2 3 4
```
예상 출력
```
22
```