Tầm nhìn tòa nhà (Tower Visibility)

Nguồn: Baekjoon Online Judge

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ tòa nhà trên một đường thẳng, đánh số từ $1$ đến $N$, khoảng cách giữa hai tòa kề nhau bằng nhau. Từ tòa $i$, chỉ xét các tòa $j$ có $L_j>L_i$. Tòa $j$ được nhìn thấy từ $i$ khi mọi tòa nằm giữa $i$ và $j$ đều thấp hơn $L_j$; nếu có một tòa ở giữa cao ít nhất bằng $L_j$ thì tòa $j$ bị che. Với mỗi tòa, hãy xác định tổng số tòa nhìn thấy ở cả hai phía và, nếu có, chỉ số tòa nhìn thấy gần nhất. Nếu có hai tòa gần nhất cùng khoảng cách, chọn chỉ số nhỏ hơn.

Input

Dòng đầu chứa $N$. Dòng thứ hai chứa $N$ chiều cao $L_1,L_2,\ldots,L_N$.

Output

Với mỗi $i$ từ $1$ đến $N$, in một dòng. Nếu không nhìn thấy tòa nào, in 0. Ngược lại, in số tòa nhìn thấy và chỉ số tòa gần nhất.

Subtask

• Subtask 1 (30 điểm): $N\le2000$; các điều kiện khác giữ nguyên.
• Subtask 2 (70 điểm): $1\le N\le10^5$, $1\le L_i\le10^5$.

Ví dụ

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

Giải thích

Các chiều cao là $3,7,1,6,3,5,1,7$.

Các tòa nhìn thấy từ từng vị trí là:

• Tòa $1$: thấy tòa $2$; có $1$ tòa, gần nhất là $2$.
• Tòa $2$: không có tòa nào cao hơn có thể nhìn thấy; in 0.
• Tòa $3$: thấy các tòa $2,4,8$; có $3$ tòa. Tòa $2$ và $4$ đều cách một vị trí, nên chọn chỉ số nhỏ hơn là $2$.
• Tòa $4$: thấy các tòa $2,8$; cả hai cách $2$ vị trí, nên chọn $2$.
• Tòa $5$: thấy các tòa $2,4,6,8$; gần nhất là $4$ và $6$, cùng cách $1$, nên chọn $4$.
• Tòa $6$: thấy các tòa $2,4,8$; gần nhất là $4$.
• Tòa $7$: thấy các tòa $2,4,6,8$; gần nhất là $6$ và $8$, cùng cách $1$, nên chọn $6$.
• Tòa $8$: không có tòa nào cao hơn có thể nhìn thấy; in 0.

Các dòng này đúng với output đã cho.