Мама подарила мальчику Диме перестановку p_1, p_2, ..., p_n целых чисел от 1 до n. А еще Дима очень любит графы. Дима хочет построить ориентированный граф, в котором не менее n вершин, в котором выполняется следующее свойство — из вершины с номером i в вершину с номером j (1 ≤ i, j ≤ n) путь существует тогда и только тогда, когда i < j и p_i > p_j. Дима еще маленький и не любит очень большие графы. Он хочет, чтобы в нем было не более 30n вершин и 30n ребер. Помогите мальчику Диме.
Первая строка содержит число n (1 ≤ n ≤ 1000). Вторая строка содержит перестановку.
В первой строке выведите числа v и e — число вершин и ребер соответственно (n ≤ v ≤ 30n, 0 ≤ e ≤ 30n). В следующих e строках выведите описания рёбер графа — два числа от 1 до v, откуда и куда идет ребро соответственно.