행복한 수열

시간 제한1.5초메모리 제한256 MB

요약

해피하지 않은 수열이 주어질 때, 인접 원소의 절댓값 차이가 1부터 N-1까지 모두 나오도록 원소 하나를 바꾸는 모든 방법을 세어 출력한다.

난이도: 보통10점 중 7점
유형: 배열, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

길이가 $N$ 인 수열에서 인접한 두 원소의 차의 절댓값이 $1$ 부터 $N-1$ 까지의 값을 모두 가지면, 이 수열을 행복한 수열이라고 한다. 예를 들어 수열 $(1, 3, 4, 2)$ 는 인접한 원소 차의 절댓값이 차례로 $(2, 1, 2)$ 이고 $3$ 이 빠져 있으므로 행복한 수열이 아니다. 반면 수열 $(3, 1, 4, 3)$ 은 인접한 원소 차의 절댓값이 $(2, 3, 1)$ 로 $1$ 부터 $3$ 까지의 수를 모두 가지므로 행복한 수열이다.

어느 날 아침, 수열 이보가 불행한 채로 잠에서 깼다. 여러분은 이보를 도울 수 있다. 이보의 원소 중 정확히 하나를 다른 정수로 바꿔서 이보를 행복하게 만들어 보자.

입력

첫째 줄에 수열의 원소 개수 $N$ 이 주어진다. 수열의 원소는 $2$ 개 이상 $1\,000\,000$ 개 이하이고, 주어지는 수열은 행복한 수열이 아니다.

둘째 줄에 수열의 원소를 나타내는 $N$ 개의 자연수가 주어진다. 각 원소는 $1\,000\,000$ 이하이다.

출력

첫째 줄에 이보를 행복하게 만드는 방법의 수 $K$ 를 출력한다.

다음 $K$ 개의 줄에는 방법을 하나씩 두 정수로 출력한다. 첫 번째 수는 바꿀 원소의 위치( $1$ 부터 $N$ 까지)이고, 두 번째 수는 그 위치에 새로 들어갈 수다. 새로 들어갈 수는 어떤 정수여도 된다(0이나 음수도 가능하다).

방법은 위치의 오름차순으로 출력하고, 위치가 같으면 새로 들어갈 수의 오름차순으로 출력한다.

예제3

예제 1
입력
```
4
1 3 5 3
```
예상 출력
```
2
2 2
2 4
```
예제 2
입력
```
3
1 1 2
```
예상 출력
```
4
1 -1
1 3
2 0
2 3
```
예제 3
입력
```
4
1 3 3 5
```
예상 출력
```
4
2 0
2 4
3 2
3 6
```