Problem: It's Petya's birthday party and his friends have presented him a brand new "Electrician-n" construction set, which they are sure he will enjoy as he always does with weird puzzles they give him.

Construction set "Electrician-n" consists of 2n - 1 wires and 2n light bulbs. Each bulb has its own unique index that is an integer from 1 to 2n, while all wires look the same and are indistinguishable. In order to complete this construction set one has to use each of the wires to connect two distinct bulbs. We define a chain in a completed construction set as a sequence of distinct bulbs of length at least two, such that every two consecutive bulbs in this sequence are directly connected by a wire. Completed construction set configuration is said to be correct if a resulting network of bulbs and wires has a tree structure, i.e. any two distinct bulbs are the endpoints of some chain.

Petya was assembling different configurations for several days, and he noticed that sometimes some of the bulbs turn on. After a series of experiments he came up with a conclusion that bulbs indexed 2i and 2i - 1 turn on if the chain connecting them consists of exactly d_i wires. Moreover, the following important condition holds: the value of d_i is never greater than n.

Petya did his best but was not able to find a configuration that makes all bulbs to turn on, so he seeks your assistance. Please, find out a configuration that makes all bulbs shine. It is guaranteed that such configuration always exists.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the parameter of a construction set that defines the number of bulbs and the number of wires.

Next line contains n integers d_1, d_2, …, d_n (1 ≤ d_i ≤ n), where d_i stands for the number of wires the chain between bulbs 2i and 2i - 1 should consist of.

Output

Print 2n - 1 lines. The i-th of them should contain two distinct integers a_i and b_i (1 ≤ a_i, b_i ≤ 2n, a_i ≠ b_i) — indices of bulbs connected by a wire.

If there are several possible valid answer you can print any of them.

Examples

Input


3
2 2 2


Output


1 6
2 6
3 5
3 6
4 5


Input


4
2 2 2 1


Output


1 6
1 7
2 6
3 5
3 6
4 5
7 8


Input


6
2 2 2 2 2 2


Output


1 3
2 3
3 5
4 5
5 7
6 7
7 12
8 12
9 11
9 12
10 11


Input


2
1 1


Output


1 2
1 4
3 4

Note

<image> Answer for the first sample test.  <image> Answer for the second sample test. 

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EPetyaAndConstructionSet solver = new EPetyaAndConstructionSet();
        solver.solve(1, in, out);
        out.close();
    }

    static class EPetyaAndConstructionSet {
        public void solve(int testNumber, FastReader s, PrintWriter out) {
            int n = s.nextInt();
            EPetyaAndConstructionSet.pair[] arr = new EPetyaAndConstructionSet.pair[n];
            for (int i = 0; i < n; i++) {
                arr[i] = new EPetyaAndConstructionSet.pair(2 * i + 1, s.nextInt());
            }


            HashMap<Integer, EPetyaAndConstructionSet.Node> leftMap = new HashMap<>();
            HashMap<Integer, EPetyaAndConstructionSet.Node> rightMap = new HashMap<>();
            HashMap<Integer, Integer> levels = new HashMap<>();
            HashSet<Integer> leftSet = new HashSet<>();
            HashSet<Integer> rightSet = new HashSet<>();
            Arrays.sort(arr);
            EPetyaAndConstructionSet.Node root = new EPetyaAndConstructionSet.Node(arr[0].from);

            root.level = 0;
            leftMap.put(0, root);
            rightMap.put(0, root);
            int count = 0;
            EPetyaAndConstructionSet.Node parent = root;
            EPetyaAndConstructionSet.Node curr;
            int i = 1;
            while (count != arr[0].val - 1) {
                curr = new EPetyaAndConstructionSet.Node(arr[i].from);
                curr.level = parent.level + 1;
                curr.left = true;
                leftSet.add(i);
                leftMap.put(curr.level, curr);
                levels.put(i, curr.level);
                parent.children.add(curr);
                parent = curr;
                count++;
                i++;
            }

            EPetyaAndConstructionSet.Node a = new EPetyaAndConstructionSet.Node(arr[0].to);
            a.level = parent.level + 1;
            a.left = true;
            parent.children.add(a);
            leftMap.put(a.level, a);
            parent = root;

//        i--;
            while (i != n) {
                curr = new EPetyaAndConstructionSet.Node(arr[i].from);
                curr.level = parent.level + 1;
                curr.left = false;
                levels.put(i, curr.level);
                rightSet.add(i);
                rightMap.put(curr.level, curr);
                parent.children.add(curr);
                parent = curr;
                count++;
                i++;
            }

            leftSet.add(0);
            rightSet.add(0);
            for (int j = 1; j < n; j++) {
                int level = levels.get(j);
                if (leftSet.contains(j)) {
                    if (level > arr[j].val) {
                        if (leftMap.containsKey(level + arr[j].val - 1)) {
                            EPetyaAndConstructionSet.Node n1 = leftMap.get(level + arr[j].val - 1);
                            EPetyaAndConstructionSet.Node newNode = new EPetyaAndConstructionSet.Node(arr[j].to);
                            newNode.left = true;
                            newNode.level = level + arr[j].val;
                            n1.children.add(newNode);
                            if (!leftMap.containsKey(newNode.level)) {
                                leftMap.put(newNode.level, newNode);
                            }
                        } else {
                            EPetyaAndConstructionSet.Node n1 = leftMap.get(level - arr[j].val + 1);
                            EPetyaAndConstructionSet.Node newNode = new EPetyaAndConstructionSet.Node(arr[j].to);
                            newNode.left = true;
                            newNode.level = level - arr[j].val;
                            n1.children.add(newNode);
                            if (!leftMap.containsKey(newNode.level)) {
                                leftMap.put(newNode.level, newNode);
                            }
                        }
                    } else {
                        if (leftMap.containsKey(level + arr[j].val - 1)) {
                            EPetyaAndConstructionSet.Node n1 = leftMap.get(level + arr[j].val - 1);
                            EPetyaAndConstructionSet.Node newNode = new EPetyaAndConstructionSet.Node(arr[j].to);
                            newNode.left = true;
                            newNode.level = level + arr[j].val;
                            n1.children.add(newNode);
                            if (!leftMap.containsKey(newNode.level)) {
                                leftMap.put(newNode.level, newNode);
                            }
                        } else {
                            EPetyaAndConstructionSet.Node n1 = rightMap.get(arr[j].val - level - 1);
                            EPetyaAndConstructionSet.Node newNode = new EPetyaAndConstructionSet.Node(arr[j].to);
                            newNode.left = true;
                            newNode.level = arr[j].val - level - 1;
                            n1.children.add(newNode);
                            if (!rightMap.containsKey(newNode.level)) {
                                rightMap.put(newNode.level, newNode);
                            }
                        }
                    }
                } else {
                    if (level > arr[j].val) {
                        if (rightMap.containsKey(level + arr[j].val - 1)) {
                            EPetyaAndConstructionSet.Node n1 = rightMap.get(level + arr[j].val - 1);
                            EPetyaAndConstructionSet.Node newNode = new EPetyaAndConstructionSet.Node(arr[j].to);
                            newNode.left = true;
                            newNode.level = level + arr[j].val;
                            n1.children.add(newNode);
                            if (!rightMap.containsKey(newNode.level)) {
                                rightMap.put(newNode.level, newNode);
                            }
                        } else {
                            EPetyaAndConstructionSet.Node n1 = rightMap.get(level - arr[j].val + 1);
                            EPetyaAndConstructionSet.Node newNode = new EPetyaAndConstructionSet.Node(arr[j].to);
                            newNode.left = true;
                            newNode.level = level - arr[j].val;
                            n1.children.add(newNode);
                            if (!rightMap.containsKey(newNode.level)) {
                                rightMap.put(newNode.level, newNode);
                            }
                        }
                    } else {
                        if (rightMap.containsKey(level + arr[j].val - 1)) {
                            EPetyaAndConstructionSet.Node n1 = rightMap.get(level + arr[j].val - 1);
                            EPetyaAndConstructionSet.Node newNode = new EPetyaAndConstructionSet.Node(arr[j].to);
                            newNode.left = true;
                            newNode.level = level + arr[j].val;
                            n1.children.add(newNode);
                            if (!rightMap.containsKey(newNode.level)) {
                                rightMap.put(newNode.level, newNode);
                            }
                        } else {
                            EPetyaAndConstructionSet.Node n1 = leftMap.get(arr[j].val - level - 1);
                            EPetyaAndConstructionSet.Node newNode = new EPetyaAndConstructionSet.Node(arr[j].to);
                            newNode.left = true;
                            newNode.level = arr[j].val - level - 1;
                            n1.children.add(newNode);
                            if (!leftMap.containsKey(newNode.level)) {
                                leftMap.put(newNode.level, newNode);
                            }
                        }
                    }
                }
            }

            Queue<EPetyaAndConstructionSet.Node> q = new LinkedList<>();
            q.add(root);
            ArrayList<EPetyaAndConstructionSet.edge> edges = new ArrayList<>();
            while (!q.isEmpty()) {
                EPetyaAndConstructionSet.Node curr1 = q.poll();
                for (EPetyaAndConstructionSet.Node node : curr1.children) {
                    edges.add(new EPetyaAndConstructionSet.edge(curr1.val, node.val));
                }
                q.addAll(curr1.children);
            }

//        out.println(edges);
            StringBuilder str = new StringBuilder();
            for (EPetyaAndConstructionSet.edge e : edges) {
                str.append(e + "\n");
            }
            out.println(str);
        }

        private static class Node {
            int val;
            ArrayList<EPetyaAndConstructionSet.Node> children;
            int level;
            boolean left;

            public Node(int val) {
                this.val = val;
                this.children = new ArrayList<>();

            }

            public String toString() {
                final StringBuilder sb = new StringBuilder("Node{");
                sb.append("val=").append(val);
                sb.append('}');
                return sb.toString();
            }

        }

        private static class edge {
            int src;
            int dest;

            public edge(int src, int dest) {
                this.src = src;
                this.dest = dest;
            }

            public String toString() {
                return this.src + " " + this.dest;
            }

        }

        private static class pair implements Comparable<EPetyaAndConstructionSet.pair> {
            int from;
            int to;
            int val;

            public pair(int from, int val) {
                this.from = from;
                this.val = val;
                this.to = from + 1;
            }

            public int compareTo(EPetyaAndConstructionSet.pair o) {
                return Integer.compare(o.val, this.val);
            }

        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}