Thành phố ByteLand dự định xây dựng \(n\) tòa nhà dọc theo một con phố. Trong bản thiết kế ban đầu, tòa nhà thứ \(i\) có \(a_i\) tầng, không có hai tòa nhà nào cùng độ cao (tính bằng số tầng). Độ đẹp của tòa nhà thứ \(i\) được tính bằng số lượng lớn nhất các tòa nhà liên tiếp xung quanh toà nhà thứ \(i\) mà thấp hơn toà đó.

Dưới sự góp ý của quần chúng, thành phố dự định sửa lại thiết kế: Một tòa nhà được sửa thành vườn hoa (toà nhà với độ cao \(0\)). Hãy giúp đội ngũ thiết kế xác định tổng độ đẹp đạt được với từng cách đặt vườn hoa.

Input

• Dòng \(1\): Số nguyên dương \(n\) \((n \leq 10^5)\)
• Dòng \(2\): \(n\) số nguyên dương \(a_1,a_2, \ldots,a_n\) \((1 \leq a_i \leq 10^9; a_i \neq a_j \forall i \neq j)\)

Output

• In ra \(n\) dòng, dòng thứ \(i\) ghi một số nguyên là tổng độ đẹp của dãy phố nếu tòa nhà \(i\) được sửa thành vườn hoa.

Example

7
10 3 1 7 8 6 5

19
22
22
22
21
22
22