Мама подарувала хлопчику Дімі перестановку 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, звідки і куди йде ребро відповідно.