Cho dãy số gồm ~N~ phần tử ~a_1, a_2, \dots, a_N~ là một hoán vị của các số nguyên từ ~1~ đến ~N~. Dãy con của một dãy số là dãy số nhận được khi không xoá phần tử nào hoặc xoá nhiều phần tử khỏi dãy số đó. Một dãy số ~b_1, b_2, \dots, b_M~ được gọi là dãy số lượn sóng khi thoả mãn điều kiện sau: Với mọi ~i \ (1\le i\le M-1)~, nếu ~b_i \lt b_{i+1}~ thì ~b_{i+1} \gt b_{i+2}~; hoặc nếu ~b_i \gt b_{i+1}~ thì ~b_{i+1} \lt b_{i+2}~. Dãy số gồm không quá ~2~ phần tử cũng là dãy số lượn sóng.

Ta gọi ~f(x, l, r)~ là số lượng phần tử của dãy con lượn sóng dài nhất của dãy số ~a_l, a_{l+1}, \dots, a_r~ sao cho tất cả các phần tử có giá trị không lớn hơn ~x~.

Đặt ~h(x) = \sum^N_{l=1} \sum^N_{r=l} f(x, l, r)~. Hãy tính các giá trị của ~h(1), h(2), \dots, h(N)~.

INPUT

• Dòng đầu tiên chứa số nguyên ~N \ (2\le N\le 2\times 10^5)~;
• Dòng thứ hai chứa ~N~ số nguyên ~a_i \ (1\le i\le n)~ là hoán vị từ ~1~ đến ~N~.

OUTPUT

Ghi trên ~N~ dòng, dòng thứ ~i \ (1\le i\le N)~ ghi một số nguyên là giá trị của ~h(i)~.

SAMPLE INPUT

4
1 3 4 2

SAMPLE OUTPUT

4
8
14
18

~h(1) = 1 + 1 + 1 + 1 + 0 + 0 + 0 + 0 + 0 + 0 = 4~

~h(2) = 1 + 1 + 1 + 2 + 0 + 0 + 1 + 0 + 1 + 1 = 8~

~h(3) = 1 + 2 + 2 + 3 + 1 + 1 + 2 + 0 + 1 + 1 = 14~

~h(4) = 1 + 2 + 2 + 3 + 1 + 2 + 3 + 1 + 2 + 1 = 18~

SUBTASKS

• Có ~20\%~ số test ứng với ~20\%~ số điểm thoả mãn: ~N\le 15~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~N \le 100~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~N \le 500~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm thoả mãn: ~N\le 5000~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm không có ràng buộc gì thêm.