Happy sequence

Time limit1.5sMemory limit256 MB

Summary

Given a non-happy sequence, count and list every single-element replacement that makes all adjacent absolute differences exactly the set 1..N-1.

Level: Medium7 of 10
Topics: Array, Hash map, Implementation
Solved: No attempts yet

Problem

A sequence of length $N$ is happy if and only if the absolute differences of its adjacent elements take every value from $1$ to $N-1$ . For example, the sequence $(1, 3, 4, 2)$ is not happy, because the absolute differences of its adjacent elements are $(2, 1, 2)$ in order, and the number $3$ is missing. On the other hand, the sequence $(3, 1, 4, 3)$ is happy, because the absolute differences of its adjacent elements are $(2, 3, 1)$ , which are all the numbers from $1$ to $3$ .

One morning, the sequence Ivo woke up unhappy. You can help it: you may replace exactly one of its elements with some other integer and make Ivo happy.

Input

The first line contains $N$ , the number of elements of the sequence. The sequence has at least $2$ and at most $1\,000\,000$ elements, and it is not happy.

The second line contains $N$ positive integers, the elements of the sequence. Every element is at most $1\,000\,000$ .

Output

On the first line, print $K$ , the number of ways to make Ivo happy.

On each of the next $K$ lines, print one way as two integers. The first is the position of the element you change (from $1$ to $N$ ), and the second is the new number at that position, which can be any integer (zero and negative numbers are allowed).

Print the ways in increasing order of position, and ways with the same position in increasing order of the new number.

Examples3

Example 1
Input
```
4
1 3 5 3
```
Expected output
```
2
2 2
2 4
```
Example 2
Input
```
3
1 1 2
```
Expected output
```
4
1 -1
1 3
2 0
2 3
```
Example 3
Input
```
4
1 3 3 5
```
Expected output
```
4
2 0
2 4
3 2
3 6
```