Dima and the permutation

Mom gave Dima a permutation (p_1, p_2, ..., p_n) of integers ranging from (1) to (n). Dima, who is very fond of graphs, wants to create a directed graph with at least (n) vertices. The graph should satisfy the following condition: there is a path from vertex (i) to vertex (j) ((1 $\le$ i, j $\le$ n)) if and only if (i < j) and (p_i > p_j). Since Dima prefers smaller graphs, he wants the graph to have no more than (30n) vertices and (30n) edges. Your task is to assist Dima in constructing such a graph.

Input

The first line contains the integer (n) ((1 $\le$ n $\le$ 1000)). The second line provides the permutation.

Output

On the first line, output the integers (v) and (e) — the number of vertices and edges, respectively ((n $\le$ v $\le$ 30n), (0 $\le$ e $\le$ 30n)). In the following (e) lines, describe the edges of the graph with two numbers each, indicating the start and end vertices of each edge.

Examples