Background

Please note that this problem has non-standard time and memory limits.

Due to differences in judge machine performance, the time limit has been adjusted to 0.5 s.

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

Problem Description

You are given a sequence $\{a_i\}$ of length $n$.

Define $f_i=\max\limits_{1 \le j<i \land a_j<a_i}\{f_j+1\}$. In particular, if there is no $1 \le j<i$ such that $a_j<a_i$, then $f_i=1$.

There is a directed edge 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 \rightarrow v$ so that the new graph after adding them is strongly connected.

Please tell her the minimum number of edges that need to be added, and construct a solution.

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

Input Format

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

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

Output Format

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

In the next $m$ lines, each line outputs two positive integers $u,v$ separated by a space, denoting an added directed edge $u \rightarrow v$.

You need to ensure that $0 \le m \le n$ and $u,v \in [1,n]$.

6
2 1 3 5 4 1

3
6 1
4 2
5 6

Hint

Translated by ChatGPT 5