Kruskal-chan loves strongly connected graphs, and she is dedicated to exploring their strong connectivity on various graphs.

Given a sequence $\{a_i\}$ of length $n$.

Let $f_i = \max_{1 \le j < i \land a_j < a_i} \{f_j + 1\}$. Specifically, if there is no $1 \le j < i$ such that $a_j < a_i$, then $f_i = 1$.

A directed edge exists between $u$ and $v$ if and only if $u < v$, $a_u < a_v$, and $f_u + 1 = f_v$.

Kruskal-chan wants to add some directed edges $u \to v$ such that the resulting graph is strongly connected.

Please tell her the minimum number of edges that need to be added and provide a construction.

Note: A graph is strongly connected if and only if for any $1 \le u, v \le n$, there exists a path from $u$ to $v$ and a path from $v$ to $u$.

Input

The first line contains a positive integer $n$ ($1 \le n \le 10^5$), representing the length of the sequence.

The second line contains $n$ integers, where the $i$-th positive integer $a_i$ ($1 \le a_i \le 10^9$) represents the $i$-th term of the sequence.

Output

The first line outputs an integer $m$, representing the minimum number of edges to add.

The next $m$ lines each output two space-separated positive integers $u, v$, representing the added directed edge $u \to v$.

It must be guaranteed that $0 \le m \le n$ and $u, v \in [1, n]$.

Examples

Input 1

6
2 1 3 5 4 1

Output 1

3
6 1
4 2
5 6