벨과 와이즈의 가게 홍보

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

"""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()

• Dependency: teflib.permcycle.permutation_cycle