Note: This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please, take a look at the sample explanation to ensure that you understand the problem correctly.

Problem statement

Given a set of N nodes, where each node has an integer A[i] associated with it. 

Construct a tree using N nodes such that the value of the given function Z is maximized.

\(Z = \sum_\limits{i = 1}^{i = N} [\sum_\limits{j = i + 1}^{j = N}[F(i,j)]]\), where \(F(i,j) = LIS(i,j) \times LDS(i,j)\)

here \(LIS(i,j) \) represents length of longest increasing subsequence on simple path starting from node i to node j and \(LDS(i,j)\) represents length of longest decreasing subsequence on simple path starting from node i to node j .

Input

• First line contains an integer N denoting number of nodes in the tree.
• Next line contains N space separated integers denoting the value of each node i.e. A[i]. 

Output

• Print N - 1 lines where each line contains
  • Two space separated integers a b denoting an edge between node a and b in the tree. 

Constraints

\(2 \le N \le 500 \\ 1 \le A[i] \le 10^9\)

Verdit and Scoring

• Z is the score for each test case.
• If the output is not a tree or contains any invalid entry, then you will receive a Wrong Answer verdict.