You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

请注意本题非常规时空限制！

题目背景

克露丝卡尔酱喜欢强连通图，她致力于在各种图上探究它们的强连通性。

题目描述

给定一个长度为 $n$ 的序列 $\{a_i\}$。

记 $f_i=\max\limits_{1 \le j<i \land a_j<a_i}\{f_j+1\}$，特别地，若不存在 $1 \le j<i$ 满足 $a_j<a_i$，则 $f_i=1$。

$u,v$ 之间存在有向边当且仅当 $u<v,a_u<a_v$ 且满足 $f_u+1=f_v$。

克露丝卡尔酱想要添加一些有向边 $u \rightarrow v$，使得添加后得到的新图强连通。

请你告诉她最少需要添加的边数并构造方案。

注：一张图是强连通的当且仅当对于任意 $1 \le u,v \le n$，$u$ 到 $v$ 和 $v$ 到 $u$ 的路径均存在。

输入格式

第一行一个正整数 $n$ $(1 \le n \le 10^5)$ 表示序列长度。

第二行 $n$ 个整数，第 $i$ 个正整数 $a_i$ $(1\le a_i\le 10^9)$ 表示序列的第 $i$ 项。

输出格式

第一行输出一个整数 $m$，表示最少添加的边数。

接下来 $m$ 行，每行输出两个以空格分隔的正整数 $u,v$，表示添加的有向边 $u \rightarrow v$。

需要保证 $0 \le m \le n$ 并且 $u,v \in [1,n]$。

样例 #1

样例输入 #1

6
2 1 3 5 4 1

样例输出 #1

3
6 1
4 2
5 6