Alice cần tạo đồ thị gồm ~n~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~n~, có các tính chất: Vô hướng; Không có khuyên (không có cạnh nối chính nó); Không có cạnh bội (giữa hai đỉnh chỉ có nhiều nhất một cạnh); Liên thông (từ một đỉnh bất kì đều có đường đi tới một đỉnh bất kì khác); Đỉnh ~i~ (~1 \le i \le n~) có bậc là ~d_i~.

Yêu cầu: Cho dãy số nguyên dương ~d_1, d_2, \dots, d_n~, hãy giúp Alice xây dựng đồ thị thỏa mãn.

Input

• Dòng đầu chứa số nguyên ~n~ (~n \le 10^4~);
• Dòng thứ hai chứa ~n~ số nguyên ~d_1, d_2, \dots, d_n~ (~0 < d_i < n; d_1 + d_2 + \dots + d_n \le 10^5~). Dữ liệu bảo đảm tồn tại đồ thị thỏa mãn.

Output

• Ghi ra một số dòng, mỗi dòng chứa hai số ~i, j~ mô tả một cạnh của đồ thị.

Subtasks

• Có ~30%~ số test của bài có ~n \le 5~;
• Có ~20%~ số test khác của bài có tính chất: ~n \le 100~ và đồ thị cần xây dựng có dạng cây;
• Có ~10%~ số test khác của bài có tính chất: Đồ thị cần xây dựng có dạng cây;
• Có ~20%~ số test khác của bài có tính chất: ~n \le 100~;
• Có ~20%~ số test còn lại của bài không có ràng buộc nào thêm.

Sample Input 1

3
2 1 1

Sample Output 1

1 2
1 3

Sample Input 2

3
2 2 2

Sample Output 2

1 2
1 3
2 3