3초 정렬

면접 대비

시간 제한2초메모리 제한1024 MB

요약

정렬되지 않은 수열이 주어질 때 원소를 3번 이하로 교체해 비내림차순으로 만들 수 있는지 판정하고, 그런 교체 방법 하나를 출력한다.

문제

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

입력받은 수열을 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번의 연산 안에 수열을 오름차순으로 정렬된 상태로 만들 수 없으면,

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