Tower Visibility

Source: Baekjoon Online Judge

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ buildings on a line, numbered $1$ through $N$, with equal spacing between adjacent buildings. From building $i$, only buildings $j$ with $L_j>L_i$ are candidates. Building $j$ is visible from $i$ if every building strictly between $i$ and $j$ has height less than $L_j$; if an intermediate building has height at least $L_j$, then $j$ is blocked. For each building, determine the total number of visible buildings on both sides and, if any exists, the index of the nearest visible building. If two nearest buildings are at the same distance, choose the smaller index.

Input

The first line contains $N$. The second line contains $N$ heights $L_1,L_2,\ldots,L_N$.

Output

For each $i$ from $1$ to $N$, print one line. If no building is visible, print 0. Otherwise print the number of visible buildings and the index of the nearest one.

Subtasks

• Subtask 1 (30 points): $N\le2000$; all other conditions are unchanged.
• Subtask 2 (70 points): $1\le N\le10^5$, $1\le L_i\le10^5$.

Examples

Input

8
3 7 1 6 3 5 1 7

Output

1 2
0
3 2
2 2
4 4
3 4
4 6
0

Explanation

The heights are $3,7,1,6,3,5,1,7$.

The visible buildings from each position are:

• Building $1$: sees building $2$; count $1$, nearest index $2$.
• Building $2$: no taller visible building; print 0.
• Building $3$: sees buildings $2,4,8$; count $3$. Buildings $2$ and $4$ are both one position away, so choose the smaller index $2$.
• Building $4$: sees buildings $2,8$; both are two positions away, so choose $2$.
• Building $5$: sees buildings $2,4,6,8$; the nearest are $4$ and $6$, both one position away, so choose $4$.
• Building $6$: sees buildings $2,4,8$; the nearest is $4$.
• Building $7$: sees buildings $2,4,6,8$; the nearest are $6$ and $8$, both one position away, so choose $6$.
• Building $8$: no taller visible building; print 0.

These counts and nearest indices give exactly the sample output.