#33 쿠키 분배하기

Statement

Statement language

처음에 $i\ (1 \leq i \leq N)$ 번 사람은 $A_i$ 개의 쿠키를 가지고 있다. 이때, $A_1 + A_2 + \cdots + A_N$ 은 $N$ 의 배수임이 보장된다.

한 번의 시행으로 양의 정수 $k \ (1 \leq k \leq N)$ 와 양의 정수 $x$ 를 골라, $k$ 번 사람이 가진 쿠키 $x$ 개를 $k + 1$ 번 사람에게 줄 수 있다. 단, 시행 직전에 $k$ 번 사람은 쿠키를 $x$ 개 이상 가지고 있어야 하며, $N + 1$ 번 사람은 $1$ 번 사람과 동일하다.

모든 사람이 동일한 개수의 쿠키를 갖도록 하는 시행 순서를 출력하여라.

Input

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1 \ A_2 \ \cdots \ A_N$

Output

시행 횟수를 $S$ 라고 하자. $i \ (1 \leq i \leq S)$ 번째 시행에서 $k_i$ 번 사람이 $k_i + 1$ 번 사람에게 쿠키 $x_i$ 개를 주었다면, 다음과 같은 형식으로 출력한다.

$S$ $k_1 \ x_1$ $k_2 \ x_2$ $\vdots$ $k_S \ x_S$

Constraints

$2 \leq N \leq 200\ 000$ .
$0 \leq A_i \leq 1 \ 000 \ 000 \ 000 \ (1 \leq i \leq N)$ .
$A_1 + A_2 + \cdots + A_N$ 은 $N$ 의 배수이다.

Subtasks

#	Score	Constraints
1	7	$N \leq 8$ , $A_i \leq 8 \ (1 \leq i \leq N)$ .
2	16	$M = \frac{A_1 + A_2 + \cdots + A_N}{N}$ 라고 할 때, $A_1,\cdots,A_t \geq M$ , $A_{t+1},\cdots,A_N \leq M$ 인 $1 \leq t \leq N - 1$ 이 존재한다.
3	24	$N \leq 2\ 000$ .
4	53	추가적인 제약조건이 없다.

Scoring

출력은 $0 \leq S \leq 5N$ , $1 \leq k_i \leq N$ , $1 \leq x_i \leq 10^{18}$ 을 만족해야 한다. 또한 각 시행 직전에 $k_i$ 번 사람은 쿠키를 $x_i$ 개 이상 가지고 있어야 하며, 모든 시행이 끝난 뒤 모든 사람의 쿠키 개수가 같아야 한다.

서브태스크 $1, 2, 3$ 에서는 위 조건을 모두 만족하면 만점을 받는다.

서브태스크 $4$ 에서는 부분 점수가 주어진다. 각 테스트케이스에 대하여 시행 횟수를 $S$ , 가능한 최소 시행 횟수를 $T$ 라 할 때 해당 테스트케이스의 점수는

3 + \dfrac{5100}{102 + S - T}

이며, 서브태스크 $4$ 의 점수는 이에 속한 모든 테스트케이스의 점수 중 최솟값이다.

Samples

Sample 1

Input

4
6 2 6 2

Output

2
3 2
1 2

이 예제는 서브태스크 1, 3, 4의 조건을 만족한다.

Sample 2

Input

5
8 0 5 7 0

Output

이 예제는 서브태스크 1, 3, 4의 조건을 만족한다.

Sample 3

Input

5
7 6 5 2 0

Output

이 예제는 서브태스크 1, 2, 3, 4의 조건을 만족한다.

Sample 4

Input

10
7 3 5 5 9 1 6 4 8 2

Output

이 예제는 서브태스크 3, 4의 조건을 만족한다.