P6854 Tram

电车开了，他的声音在我的脑海中萦绕不散： 「留下来，跟我来。」 我回头去看车站，他不见了。 我在德辅道寻找他的身影。 路人不多，但他却消失了。 我把窗拉下来，微风轻拂我的脸。 他到哪儿去了？ 路人、街道、高楼大厦。 在我身边轻轻地流走。

你就要出道了！ 你的教练和同学为你联系了摄影师，你们来到德辅道边拍宣传照。 街上一共有 $n$ 幢楼房，从左到右排成一列，从 $1$ 到 $n$ 编号，编号为 $i$ 的楼房的高度是 $a_i$。 一张照片可以用二元组 $(l,r)$ 描述，其中 $1\le l\le r\le n$，这张照片中包含了编号在 $[l,r]$ 之间的所有楼房。 摄影师认为，一张照片是美丽的，当且仅当其同时满足下面的两个条件： - 对于任意的 $i

无

无

**本题采用捆绑测试**。你只有通过 subtask 中的所有测试点才能获得该 subtask 的分数。 - Subtask 1(10 points)：$n\le 200$； - Subtask 2(5 points)：$n\le 1000$； - Subtask 3(10 points)：$n\le 6000$； - Subtask 4(20 points)：$n\le 3\times 10^4$； - Subtask 5(30 points)：$n\le 10^5$； - Subtask 6(25 points)：$n\le 10^6$。 对于所有数据满足：$1\le n,a_i\le 10^6$。 注意答案的大小可能超过 $32$ 位有符号整数的范围。 本题输入数据量较大，请使用较快的读入方式。