You're given an array ~a~ of ~N~ elements. For each element ~a_i~, determine the maximum length subarray ~[l, r], 1 \le l \le i \le r \le N~ such that ~a_i~ is strictly the largest value.

Constraints

For all subtasks,

~1 \le N \le 5 \times 10^5~

~1 \le a_i \le 10^9~

Subtask 1 [15%]

~1 \le N \le 2 \times 10^3~

Subtask 2 [85%]

No additional constraints.

Input specification

The first line of input will contain ~N~.

The next line will contain ~N~ space-separated integers ~a_i~.

Output specification

Output ~N~ lines each containing ~2~ integers. On the ~i~-th line, output the values of ~l~ and ~r~ for ~a_i~.

Sample Input

6
1 4 6 5 2 2

Sample Output

1 1
1 2
1 6
4 6
5 5
6 6