시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 1024 MB273605025.510%

문제

지금 여러분이 평화롭게 문제를 보고 있는 사이, 이미 강당 밖에는 극단 원리주의 민초파 테러리스트 김준원이 학교를 점령했다.

입력받은 수열을 3초 안에 오름차순으로 정렬된 상태로 만들지 않으면 강당에 설치해놓은 민초 폭탄이 터진다.

당신은 수열의 어떤 원소 $A_i$를 다른 수 $X$로 바꿀 수 있다.

이 연산에는 1초가 걸린다.

3...

2...

1...

입력

첫째 줄에 당신이 정렬된 상태로 만들어야 하는 수열의 길이 $N$이 주어진다.

둘째 줄에 수열의 원소들을 나타내는 $N$개의 정수 $A_1, A_2, \cdots , A_N$이 공백으로 구분되어 주어진다.

출력

3번의 연산 안에 수열을 오름차순으로 정렬된 상태로 만들 수 있으면,

  • 첫째 줄에 YES를 출력한다.
  • 둘째 줄부터, 수열을 정렬된 상태로 만들 수 있는 방법을 다음과 같은 형태로 출력한다.
    • 첫째 줄에, 연산 횟수 $K$를 출력한다.
    • 이후, $K$개의 줄에 걸쳐, 적용할 연산을 순서대로 출력한다.
      구체적으로, 각 줄에 두 정수 $i$와 $X$를 출력한다. 이는, 원소 $A_i$를 $X$로 바꾸는 연산을 의미한다. ($1 \le i \le N$, $1 \leq X \leq 1\,000\,000\,000$)

연산의 횟수를 최소화할 필요가 없으며, 가능한 방법이 여럿 있으면 아무 방법이나 하나 출력해도 괜찮다. 같은 원소를 여러 번 수정해도 된다.

3번의 연산 안에 수열을 오름차순으로 정렬된 상태로 만들 수 없으면,

  • 첫째 줄에 NO를 출력한다.

제한

  • $1 \leq N \leq 200\,000$
  • $1 \leq A_i \leq 1\,000\,000\,000$ ($1 \le i \le N$)
  • 이미 오름차순으로 정렬된 수열은 주어지지 않는다.

예제 입력 1

5
6 7 10 8 20

예제 출력 1

YES
1
4 15

원래 수열인 A = [6, 7, 10, 8, 20]의 4번째 원소인 8을 15로 바꾸면 A = [6, 7, 10, 15, 20]이 되어 오름차순으로 정렬된 배열이 된다.

3번째 원소인 10을 8로 바꾸어도 A = [6, 7, 8, 8, 20]이 되어 오름차순으로 정렬된 배열이 되므로 아래와 같이 출력해도 정답으로 인정된다.

YES
1
3 8

예제 입력 2

3
9 1 7

예제 출력 2

YES
3
1 1
2 2
3 3

배열의 첫번째 원소를 1로, 두번째 원소를 2로, 세번째 원소를 3으로 바꾸면 A = [1, 2, 3]이 되어 오름차순으로 정렬된 배열이 된다.

연산의 횟수를 최소화할 필요는 없다!

예제 입력 3

10
10 9 8 7 6 5 4 3 2 1

예제 출력 3

NO

이 배열은 3번의 연산 안에 오름차순으로 정렬할 수 없다. 따라서 이 배열이 입력으로 주어지면 김준원의 테러를 막을 수 없다.

노트

수열 $A_1, \cdots, A_N$이 오름차순으로 정렬되어 있다는 것은, $A_1 \le A_2$, $A_2 \le A_3$, $\cdots$, $A_{N-1} \le A_N$이라는 뜻이다.

출처

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