길 위의 순열: Alice

Alice와 Bob은 지역에서 열리는 여러 프로그래밍 대회에 가기 위해 자주 장거리 여행을 떠난다. 그들이 사는 주에서는 모든 것이 더 크기 때문에, 두 사람은 시간을 보내려고 차 안에서 할 게임을 만들었다.

Alice와 Bob은 둘 다 컴퓨터 과학자라서 "숫자 맞히기" 게임에 금방 흥미를 잃었다. 숫자를 맞히는 사람이 로그 횟수의 추측만으로 항상 답을 찾아낼 수 있기 때문이다. 난이도를 높이려고 두 사람은 새 게임 "순열 맞히기"를 만들었다.

길이 $N$의 순열은 $1, \dots, N$을 나열한 것이다. 순열 $P$에 대해 $\text{inv}(l, r)$을 $l \leq i \leq j \leq r$이고 $P_i > P_j$인 쌍 $(i, j)$의 개수로 정의한다.

이 게임에서 Alice는 순열 하나를 생각하고, Bob은 Alice에게 함수 $\text{inv}$의 값을 최대 $N$번 물어볼 수 있다.

Alice는 이미 자신의 순열 $P$를 생각해 두었다. Bob의 질문에 아무 생각 없이 답하던 Alice는 다른 문제를 떠올린다. 모든 $l$과 $r$에 대한 $\text{inv}(l, r)$의 합은 얼마일까?

첫째 줄에 순열의 길이 $N$($1 \leq N \leq 100\,000$)이 주어진다. 둘째 줄에 Alice의 순열 $P$를 이루는 $N$개의 정수가 공백으로 구분되어 주어진다.

모든 $l$과 $r$에 대한 $\text{inv}(l, r)$의 합을 정수 하나로 출력한다. 답은 부호 있는 $64$비트 정수 범위에 들어감이 보장된다.

첫 번째 예시에서는 역전 쌍이 없다.

두 번째 예시에서는

• $\text{inv}(1, 1) = 0$.
• $\text{inv}(1, 2) = 0$.
• $\text{inv}(1, 3) = 1$.
• $\text{inv}(2, 2) = 0$.
• $\text{inv}(2, 3) = 1$.
• $\text{inv}(3, 3) = 0$.

이 값들을 모두 더하면 $2$가 된다.