Gondola Replacement

Time limit1sMemory limit256 MB

Summary

Given the n cars seen on a circular gondola line, find one possible order of breakdowns that explains the observed numbers.

Level: Medium5 of 10
Topics: Sorting, Hash map
Solved: No attempts yet

Problem

A gondola line has $n$ cars numbered $1$ to $n$ moving on a circular track. After car $i$ passes the station, car $i+1$ passes next (and car $1$ follows car $n$ ). A broken car is replaced at the same spot by spare cars numbered $n+1$ , $n+2$ , and so on in order. A gondola sequence lists the $n$ car numbers seen at the station starting from some moment. A replacement sequence lists the original car numbers that broke, in breakdown order. Given a valid gondola sequence, output one replacement sequence that could produce it.

Input

The first line contains $n$ . The second line contains the gondola sequence of length $n$ .

Output

Print the length $l$ of the replacement sequence. If $l>0$ , print the sequence on the same line separated by spaces.

Constraints

$2 \leq n \leq 100{,}000$
The input sequence is always a valid gondola sequence.

Examples1

Example 1
Input
```
2
3 2
```
Expected output
```
1 1
```