Mã Prüfer của một cây gồm \(n\) đỉnh là một dãy gồm \(n-2\) số nguyên chỉ xác định duy nhất một cấu trúc của cây.

Đoạn mã được hình thành như sau: Khi vẫn còn ít nhất ba đỉnh trên cây, tìm đỉnh lá có chỉ số nhỏ nhất, thêm chỉ số của đỉnh kề duy nhất của nó vào đoạn mã, và bỏ đỉnh lá đó ra khỏi cây.

Cho một mã Prüfer của một cây, nhiệm vụ của bạn là xây dựng lại cây ban đầu.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) là số lượng đỉnh của cây. Các đỉnh được đánh số từ \(1\) đến \(n\).
• Dòng thứ hai chứa \(n-2\) số nguyên là mã Prüfer.

Output

• In ra \(n-1\) dòng mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên \(a\) và \(b\) có ý nghĩa là có một cạnh nối giữa hai đỉnh \(a\) và \(b\). Bạn có thể in các cạnh theo thứ tự bất kỳ.

Constraints

• \(3 \le n \le 2 \times 10^5\)
• \(1 \le a, b \le n\)

Example

Sample input

5
2 2 4

Sample output

1 2
2 3
2 4
4 5