시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 10 0 0 0.000%

문제

항상 말썽을 일으키는 청개구리는 밤새 논으로 뛰어 들어 벼를 밟곤 한다.농부는 아침에 벼가 쓰러진 상태를 보고 밤새 몇 마리의 청개구리가 논을 지나갔는지 알아내려고 한다.

논에는 벼가 일직선으로 심어져 있다. 각각의 벼가 심어진 지점에 남겨진 흔적을 살피면 그 지점을 몇 마리의 청개구리가 밟고 지나갔는지를 알 수 있다. 예를 들어 벼가 심어진 지점과 각 지점을 밟고 지나간 청개구리의 수가 <그림 1>과 같다고 하자.(원은 벼가 심어진 지점, 원 안의 숫자는 밟고 지나간 청개구리의 수이다.)

모든 청개구리는 논의 왼쪽에서 들어와 일정한 간격으로 뛰어 벼를 밟고 오른쪽으로 나간다. 가장 왼쪽 지점부터 청개구리가 처음 밟는 지점까지의 간격은 청개구리의 뛰는 간격보다 작다. 중간에 방향을 바꾸는 경우는 없으며 벼가 심어진 지점 이외에 다른 지점을 밟는 경우도 없다. 청개구리의 뛰는 간격은 한계가 있어 6이하이고, 또한 논에 들어오면 적어도 두 곳을 밟아야 밖으로 나갈 수 있다. 

<그림 1>과 같은 모습은 네 마리의 청개구리가 들어와 <그림 2>와 같이 논을 밟고 나가면 생길 수 있다.

다섯 마리의 청개구리가 들어와 < 그림3> 과 같이 논을 밟고 나가도 <그림 1>과 같은 모습이 가능하다.

벼가 심어진 각 지점마다 지나간 청개구리의 수가 주어질 때, 밤새 지나간 최소 청개구리 수와 이들 각각이 어떻게 지나갔는지 그 경로를 구하여 출력하는 프로그램을 작성 하시오.

입력

첫째 줄에는 벼가 심어진 지점의 개수 N이 주어진다. 둘째 줄에는 몇 마리의 청개구리가 각각의 지점을 밟고 지나갔는지가 가장 왼쪽 지점부터 차례대로 주어진다. N은 2이상 200이하이고, 청개구리의 수는 100이하이다. 청개구리가 각 지점을 밟고 지나간 수 사이에는 한 칸의 공백이 있다. 답이 없는 경우는 없다.

출력

첫째 줄에는 밤새 지나간 최소 청개구리 수 M를 출력한다. 둘째 줄부터 M+1줄까지 M개의 줄에는 각각의 청개구리가 처음 밟고 지난간 지점이 왼쪽에서 몇 번째 지점인지와 청개구리의 뛴 간격이 얼마인지를 한 간의 공백을 사이에 두고 차례로 출력한다. 청개구리가 뛴 방법을 출력할 때 출력하는 순서는 상관이 없고 최소 청개구리 수가 되는 방법이 둘 이상일 경우 그중 하나만 출력한다.

예제 입력

8
2 1 2 1 2 0 3 1

예제 출력

4
1 2
1 3
2 3
3 4

힌트