~N~ người lính xếp thành một hàng thẳng dài. Người lính đứng ở vị trí thứ ~i~ có cao là ~h_i~. Người chỉ huy yêu cầu mỗi người lính phải chỉ ra người phía trước gần nhất và người đứng sau gần nhất cao hơn người đó. Tuy nhiên, sau khi hỏi được vài người, người chỉ huy thấy mất quá nhiều thời gian nên muốn nhờ các bạn lập trình xác định giúp câu trả lời của tất cả ~N~ người.

Input

• Dòng đầu là số tự nhiên ~N\ (N \leq 10^6)~.
• Dòng thứ 2 chứa ~N~ số nguyên dương ~h_1, h_2, \dots, h_n\ (h_i \leq 10^9)~.

Output

• Gồm ~N~ dòng, với dòng thứ ~i~ là 2 số chỉ vị trí người đứng trước và người đứng sau gần nhất cao hơn người ở vị trí thứ ~i~. Nếu vị trí nào không tồn tại, ghi ra số 0 tương ứng.

Example

Input

5
5 3 2 3 6

Output

0 5
1 5
2 4
1 5
0 0