위문공연

• 전략대로 병사를 움직여보면서 총 이동횟수의 규칙을 찾아보자. 사이클 단위로 총 이동횟수가 결정되고, 사이클 크기에 따른 총 이동횟수는 {사이클 크기}*3 - 2 가 된다. 그러면 N명의 병사들이 k개의 사이클로 나뉘어졌을 경우에 총 이동횟수는 3*N-2*k 가 된다. 사이클 갯수에 따라서 이동횟수가 결정된다!
• 이제 병사 둘이 교환을 했을때 사이클 크기가 어떻게 바뀌는지를 조사해 보자. 같은 사이클 안에 있는 병사들끼리 교환하면, 그 사이클이 두개의 사이클로 나눠진다. 그래서 총 사이클의 갯수는 1 늘어난다. 다른 사이클에 있는 병사들끼리 교환하면, 두 사이클이 하나도 합쳐진다. 총 사이클의 갯수는 1 줄어든다.
• 병사 2명을 뽑았을때 그 두명이 같은 사이클 안에 있는 경우의 수는, {둘다 1번 사이클에 있는 경우의 수} + {둘다 2번 사이클에 있는 경우의 수} + …+ {둘다 i번 사이클에 있는 경우의 수} 이다. 사이클의 크기를 s1,s2,…,sn이라 하면 s1*(s1-1)/2 + s2*(s2-1)/2 + … + sn*(sn-1)/2 과 같은 식으로 구해줄수 있다. 병사 2명이 다른 사이클에 있는 경우의 수는 전체 경우의 수에서 앞에서 계산한 값을 빼면 된다.
• 이제 구할 값은 다 구했다. 최종 답은 {두명이 같은 사이클 안에 있는 경우의 수} * (3*N - 2*({현재 사이클 갯수} + 1) + {두명이 다른 사이클 안에 있는 경우의 수} * (3*N - 2*({현재 사이클 갯수} - 1) 로 구할수 있다.
• 시간복잡도는 사이클로 분할하는데 걸리는데 O(n)이 걸린다.

"""Solution code for "BOJ 27117. 위문공연".

- Problem link: https://www.acmicpc.net/problem/27117
- Solution link: http://www.teferi.net/ps/problems/boj/27117

Tags: [math]
"""


def main():
    N = int(input())
    t = [int(x) - 1 for x in input().split()]  # pylint: disable=unused-variable

    cycle_sizes = []
    visited = [False] * N
    for i, visited_i in enumerate(visited):
        if visited_i:
            continue
        cur = i
        size = 1
        while (cur := t[cur]) != i:
            visited[cur] = True
            size += 1
        cycle_sizes.append(size)

    cycle_count = len(cycle_sizes)
    same_cycle_exchange = sum(s * (s - 1) // 2 for s in cycle_sizes)
    different_cycle_exchange = N * (N - 1) // 2 - same_cycle_exchange
    answer = (N * 3 - 2 * (cycle_count + 1)) * same_cycle_exchange
    answer += (N * 3 - 2 * (cycle_count - 1)) * different_cycle_exchange

    print(answer)


if __name__ == '__main__':
    main()