解读图腾

穿过铁门，是一片由发光石柱组成的广场。石柱排列成一排，高低不一，像是一群沉默的哨兵。Echo说这些石柱是Zero的"图腾"——每根石柱代表一个历史时刻的能量峰值。

"要解读图腾。"Echo飘到第一根石柱前，"找出有多少对石柱可以互相看见——中间没有更高的石柱挡住。"

"咋个找？"CC问，"一个个看？"

"从右往左看。"你说，"每根石柱往右看，能被它看见的石柱必须比它矮，而且中间不能有更高的。这像站岗——矮的站在高的前面，高的挡住后面所有的。"

"那就维护一排站岗的哨兵。"你说，"从右往左走，每遇到一根石柱，就把比它矮的哨兵撤掉——因为它们被挡住了。然后这根石柱自己站上去，成为新的哨兵。站岗的哨兵数量，就是能看见的对数。"

CC在旁边看着，忽然说："这就像……排队买饭。高的站在前面，矮的躲在后面，只能看见前面那个最高的。"

"差不多。"

你开始写。从右往左扫描，维护一个严格递增的哨兵队列。每遇到一根石柱，弹出队列里所有比它矮的——它们被挡住了。然后把它压进队列。队列的长度就是当前能看见的对数。

屏幕上跳出了结果。第47号石柱——最高的一根——能看见47根石柱。

"又是47。"CC说。

"最高的一根。"Echo说，"它站在最前面，挡住了后面所有的视线。"

"但它也能看见所有人。"你说。

"对。"Echo说，"看见所有人，也被所有人仰望。"

题目描述

$n$ 根石柱，高度已知。求有多少对 $(i, j)$（$i < j$），使得 $i$ 和 $j$ 之间没有比 $a_j$ 更高的石柱。

输入格式

$n$。然后 $n$ 个高度。

输出格式

能看见的对数。

输入样例

3
1 2 3

输出样例

0 0

提示

• 单调栈。从右往左扫描，维护严格递减的栈。
• 每个元素入栈前，弹出所有比它小的元素。
• 栈的大小即为能看见的对数。

图腾解读完毕，广场尽头出现了一座高架桥——不是普通的桥，是由能量束编织成的通道。Echo飘到桥头，投影被能量束的光芒切割成碎片。

"下一关。"她说，"是构筑篱笆。"

"篱笆？"CC问。

"对。"Echo说，"用能量束围成一圈篱笆，把G-30的核心区域围起来。篱笆的高度要够高，挡住所有外来的入侵者。"

"那不就是找最高的连续段？"你说。

"对。"Echo说，"但不是简单的高——是连续的高。如果中间有一段塌陷了，整个篱笆就断了。"