위문공연

위문공연이 찾아왔다! 총 $N$명의 병사가 공연을 보러 가기로 했다. 각 병사는 $1$번부터 $N$번까지의 좌석 번호 중 서로 겹치지 않게 원하는 좌석 번호를 하나 고른 뒤, 티켓이 배부되기를 기다린다.

그런데 소란을 우려한 공연장 측이 티켓을 무작위로 나누어 준 탓에, 원하는 좌석의 티켓을 받지 못한 병사가 많이 생겼다. 화가 난 병사들은 다음 방식으로 착석하기로 약속하였다.

1. 자신의 티켓에 적힌 번호의 좌석으로 이동한다. 그 좌석이 자신이 원하는 좌석이면 바로 앉는다.
2. 티켓에 적힌 번호의 좌석에 아무도 없으면, 자신이 원하는 좌석으로 이동해서 앉는다.
3. 티켓에 적힌 번호의 좌석에 누군가 앉아 있으면, 그 병사와 티켓을 교환한 뒤 1로 돌아간다.

이 방식대로 $1$번 좌석을 원하는 병사부터 $N$번 좌석을 원하는 병사까지 순서대로 한 명씩 착석하면, 모두 자신이 원하는 좌석에 앉을 수 있다.

도훈이는 이 방식으로 움직였을 때 병사들의 총 이동 횟수를 계산하는 프로그램을 작성했다. 그런데 어떤 두 병사가 몰래 티켓을 맞바꾸었다는 소식을 들었다. 누가 맞바꾸었는지 알 수 없었던 도훈이는 티켓을 맞바꿀 수 있는 $\frac{N(N-1)}{2}$가지 경우 모두에 대해 이동 횟수를 구하려 했으나, 프로그래밍 실력이 부족해 프로그램 작성에 실패했다.

티켓이 뒤바뀐 모든 $\frac{N(N-1)}{2}$가지 경우에 대해, 병사들의 이동 횟수 총합을 구하라.

시간 제한: 1초. 메모리 제한: 1024MB.

첫 번째 줄에 병사의 수 $N$이 주어진다. $(2 \leq N \leq 100000)$

두 번째 줄에 $N$개의 정수 $t_1, t_2, \ldots, t_N$이 공백으로 구분되어 주어진다. $t_i$는 $i$번 좌석을 원하는 병사가 받은 티켓 번호이다. $(1 \leq t_i \leq N)$

티켓 번호가 중복되어 주어지는 경우는 없다.

병사들이 $1$번 좌석을 원하는 병사부터 $N$번 좌석을 원하는 병사까지 차례대로 입장했을 때, 티켓을 맞바꿀 수 있는 모든 $\frac{N(N-1)}{2}$가지 경우에 대한 병사들의 이동 횟수 총합을 출력한다.