You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

信号塔

题目描述

王国边境的夜幕降临时，n 座信号塔从左到右排成一排，从左到右编号为 1 到 n，第 i 座塔的高度为 h_i。守塔人点亮塔顶的信号灯，让每座塔向右发出一道信号。

信号贴着自己塔顶的高度直线向右飞行：比它矮的塔拦不住它，信号会从矮塔的头顶掠过；而任何一座高度不低于它的塔都能拦下它——等高的塔刚好与信号同高，自然也拦得住。

• 如果右边存在高度不低于它的塔，信号会被右边第一座高度不低于它的塔吸收。信号从第 i 座塔传播到第 j 座塔，传播距离为 j - i。
• 如果右边没有高度不低于它的塔，信号会飞过整条队列，在队列的最右端消失，传播距离为 n - i。

例如，第 3 座塔的信号被第 7 座塔吸收，传播距离就是 7 - 3 = 4。

见习守塔人阿信负责登记今晚的信号账本：所有 n 座塔的信号传播距离的总和是多少？请你帮他把这个数算出来。

输入格式

第一行一个整数 n，表示信号塔的数量。

第二行 n 个整数 h_1, h_2, ..., h_n，表示每座塔的高度。

输出格式

输出一行一个整数，表示所有塔的信号传播距离的总和。

样例

输入

6
1 5 2 3 3 1

输出

8

样例解释

六座塔的高度依次为 1 5 2 3 3 1：

• 1 号塔（高度 1）：右边第一座不低于它的塔是 2 号塔（高度 5），传播距离 1。
• 2 号塔（高度 5）：右边没有不低于它的塔，信号传到最右端，传播距离 4。
• 3 号塔（高度 2）：右边第一座不低于它的塔是 4 号塔（高度 3），传播距离 1。
• 4 号塔（高度 3）：右边第一座不低于它的塔是 5 号塔，5 号塔的高度也是 3，等高的塔同样会吸收信号，传播距离 1。
• 5 号塔（高度 3）：右边只有 6 号塔（高度 1，比它矮），没有不低于它的塔，信号传到最右端，传播距离 1。
• 6 号塔：它已经是最后一座塔，传播距离 0。

总和为 1 + 4 + 1 + 1 + 1 + 0 = 8。

数据范围

1 <= n <= 500000，1 <= h_i <= 1000000000。

答案可能超出 32 位整数的表示范围，请使用 64 位整数存储与输出。