27117번 - 위문공연

위문공연이 찾아왔다! 총 $N$명의 병사들이 위문공연을 보러 가기로 했으며, 각자 본인이 원하는 $1$번부터 $N$번까지의 서로 다른 좌석 번호를 고른 뒤 티켓 배부만을 기다리고 있었다.

그러나 소란을 우려한 공연장 측에서 병사들에게 무작위로 티켓을 나누어 달라고 요청하였고, 자신이 원하는 좌석의 티켓을 받지 못한 병사들이 속출하고 말았다! 분노한 병사들은 다음과 같은 전략으로 착석하기로 약속하였다.

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

위 방식으로 한 명씩 순서대로 좌석에 착석하면, 모두가 본인이 원하는 좌석에 앉을 수 있다.

문득 위 전략대로 움직였을 때 병사의 총 움직임 횟수가 몇 번이나 될지 궁금했던 도훈이는 $1$번 좌석을 원하는 병사부터 $N$번 좌석을 원하는 병사까지 순서대로 공연장에 입장했을 때의 총 이동 횟수를 계산하는 프로그램을 작성하였다.

본인이 작성한 프로그램이 자랑스러워 다른 병사들에게 자랑하러 다니려던 차에, 도훈이는 어떤 병사 두 명이 비밀리에 서로 티켓을 맞바꾸었다는 사실을 듣게 되었다. 누가 티켓을 맞바꾸었는지 알 수 없었던 도훈이는 티켓을 맞바꿀 수 있는 ${N(N-1)}\over{2}$가지의 모든 경우에 대해 병사들이 움직이는 횟수를 구하는 프로그램을 작성하려고 했으나, 프로그래밍 실력의 부족으로 인해 프로그램 작성에 실패하여 절망하고 있다.

절망한 도훈이를 위해 티켓이 뒤바뀐 모든 ${N(N-1)}\over{2}$가지의 경우에 대하여 병사들의 이동 횟수의 총합을 알려주자.

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

두 번째 줄에 $N$개의 정수가 공백으로 구분되어 주어지며, $i$번째 숫자는 $i$번째 좌석을 원하는 병사가 받은 티켓 번호 $t_i$를 의미한다. $(1\leq t_i\leq N)$

티켓 번호가 중복되는 입력은 주어지지 않는다.

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