시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 1024 MB194746744.079%

문제

$N$개의 서로 다른 정수를 가진 배열 $A$가 주어진다.

당신은 어제 공격력이 양의 정수 $k$인 칼을 받았다. 이 칼이 있으면 배열에 아래와 같은 연산을 적용할 수 있다.

  1. 배열을 $k$개의 조각으로 자른다.
  2. $k$개의 조각을 원하는 순서대로 재배열한다.
  3. 재배열한 순서대로 조각들을 다시 합친다.

당신은 배열 $A$에 이 연산을 원하는 횟수만큼 적용하여 (한 번도 적용하지 않아도 괜찮다) 오름차순으로 정렬하려고 한다.

$k$의 값에 따라 이 연산을 적절히 적용하면 $A$를 정렬하는 것이 가능할 수도 있고, 연산을 어떻게 잘 적용해도 정렬할 수 있는 방법이 없을 수도 있다.

이 때, 배열 $A$를 정렬할 수 있는 가장 작은 양의 정수 $k$의 값을 구하는 프로그램을 작성하자.

입력

첫째 줄에 배열의 길이 $N$이 주어진다.

둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots , A_n$이 공백으로 구분되어 주어진다.

출력

주어진 수열을 오름차순으로 만들 수 있는 가장 작은 양의 정수 $k$의 값을 출력한다.

제한

  • $1 \leq N \leq 200\,000$
  • $1 \leq A_i \leq 200\,000$
  • $i \neq j$이면 $A_i \neq A_j$, 즉 배열 $A$의 값들은 모두 서로 다르다.

예제 입력 1

5
1 2 3 4 5

예제 출력 1

1

예제 입력 2

6
4 5 6 1 2 3

예제 출력 2

2

4 5 6 / 1 2 3으로 나눈 뒤, 1 2 3 / 4 5 6으로 재배열하면 된다.

예제 입력 3

6
3 4 5 6 1 2

예제 출력 3

2

3 / 4 5 6 1 2

4 5 6 / 1 2 3

1 2 3 4 5 6

출처

High School > 선린인터넷고등학교 > 제5회 천하제일 코딩대회 본선 C번