Đề bài

Khôi là một học sinh học rất kém môn Tiếng Anh. Vậy nên để lấy lại gốc, cậu cần phải học lại các thì cơ bản trong Tiếng Anh. Vì hôm qua cậu đã học xong thì Hiện tại nên môn này bạn chuyển sang học dạng tiếp theo là thì Quá khứ và Tương lai.

Cậu tự đặt ra một mô tả định nghĩa về cặp số Quá khứ - Tương lai trong mảng cho sẵn.

Cụ thể: Số Quá khứ - Tương lai của phần tử i được định nghĩa rằng là cặp số (L, R) thỏa mãn:

• L là vị trí nhỏ nhất sao cho \(L \leq i\) và \(a_k \leq a_i\) với mọi \(k \in [L, i]\).
• R là vị trí lớn nhất sao cho \(R \geq i\) và \(a_k \leq a_i\) với mọi \(k \in [i, R]\).

Yêu cầu

Cho một mảng gồm N số nguyên dương a (\(a_i \leq 10^6\)).
Với mỗi vị trí i \((i \in [1, N])\), hãy tìm ra cặp số Quá khứ - Tương lai.

Dữ liệu vào

• Dòng đầu ghi số nguyên dương N \((1 \leq N \leq 5 \times 10^5)\).
• Dòng sau ghi N số nguyên dương a \((a_i \leq 10^6)\).

Dữ liệu ra

• Đưa ra màn hình N dòng, mỗi dòng gồm 2 số nguyên dương (L, R) là số Quá khứ - Tương lai của phần tử i.

Sample Input 1

9
1 2 3 2 4 5 2 6 9

Sample Output 1

1 1
1 2
1 4
4 4
4 5
5 5
1 7
7 7
1 9

Giải thích

• Ở vị trí 1, giá trị nhỏ nhất là 1, không có số nào nhỏ hơn nó ở bên trái, nên \(L = 1\) và \(R = 1\).
• Ở vị trí 2, giá trị 2 là lớn nhất từ 1 → 2, nên \(L = 1\), \(R = 2\).
• Ở vị trí 3, giá trị 3 là lớn nhất từ 1 → 3, nhưng khi đến vị trí 4, giá trị nhỏ hơn xuất hiện, nên \(R = 4\).
• Quá trình tiếp tục với các phần tử còn lại trong mảng.