====== 벨과 와이즈의 가게 홍보 ======

===== 풀이 =====
  * 웅나한 bangboo들의 수가 최대가 되는 경우는, bangboo들이 정렬되어 있을 때이다. 오름차순 또는 내림차순 두가지로 정렬이 가능하다.
    * 이 경우에 양 끝의 bamboo들을 제외한 나머지는 모두 웅냐하다. 즉, 웅냐한 bangboo들의 수는 N-2개.
  * 오름차순 정렬에 필요한 최소 스왑 횟수는 N-{순열 사이클 개수} 이고, 이는 O(n)에 계산 가능하다.
    * [[ps:tutorial:정렬]] 참고
  * 내림차순으로 정렬하는 것은, 원소를 역순으로 배열한 뒤에 오름차순으로 정렬하는 것과 동일하다. 배열을 뒤집은 뒤에 같은 방식으로 계산해주면 된다.
  * 둘중에서 적은 횟수를 취하면 된다. 시간복잡도는 O(n)


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 34078. 벨과 와이즈의 가게 홍보".

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

Tags: [permutation cycle]
"""

from teflib import permcycle


def main():
    N = int(input())
    a = [int(x) - 1 for x in input().split()]

    min_time = N - max(
        len(permcycle.permutation_cycles(a)),
        len(permcycle.permutation_cycles(a[::-1])),
    )
    print(N - 2, min_time)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:permcycle#permutation_cycle|teflib.permcycle.permutation_cycle]]

{{tag>BOJ ps:problems:boj:골드_3}}