Dima and the permutation#2934
Dima's mother gave him a permutation p_1, p_2, \ldots, p_n of integers from to . Dima is very fond of graphs and wants to create a directed graph with at least vertices, which satisfies the following property: there is a path from vertex to vertex (1 \leq i, j \leq n) if and only if i < j and p_i > p_j. Dima does not like very large graphs and wants there to be at most vertices and edges. Help Dima construct such a graph.
The first line contains the integer (1 \leq n \leq 1000). The second line contains the permutation.
On the first line, output the integers and — the number of vertices and edges, respectively (n \leq v \leq 30n, 0 \leq e \leq 30n). In the next lines, output the descriptions of the edges of the graph — for each edge, two integers from to , indicating the start and end vertices, respectively.
Example 1