题目背景

电车开了，他的声音在我的脑海中萦绕不散：

「留下来，跟我来。」

我回头去看车站，他不见了。

我在德辅道寻找他的身影。

路人不多，但他却消失了。

我把窗拉下来，微风轻拂我的脸。

他到哪儿去了？

路人、街道、高楼大厦。

在我身边轻轻地流走。

题目描述

你就要出道了！

你的教练和同学为你联系了摄影师，你们来到德辅道边拍宣传照。

街上一共有 $n$ 幢楼房，从左到右排成一列，从 $1$ 到 $n$ 编号，编号为 $i$ 的楼房的高度是 $a_i$。

一张照片可以用二元组 $(l,r)$ 描述，其中 $1\le l\le r\le n$，这张照片中包含了编号在 $[l,r]$ 之间的所有楼房。

摄影师认为，一张照片是美丽的，当且仅当其同时满足下面的两个条件：

• 对于任意的 $i<j<k$，如果高度为 $i$ 和 $k$ 的楼房都在照片中出现过，那么高度为 $j$ 的楼房也在照片中出现过。
• 对于任意的 $i$，高度为 $i$ 的楼房要么不出现在照片中，要么在照片中出现恰好 $i$ 次。

摄像师问你，一共能拍出多少不同的美丽的照片呢？

两张照片 $(l_1,r_1)$ 和 $(l_2,r_2)$ 不同，当且仅当 $l_1\ne l_2$ 或 $r_1\ne r_2$。

输入格式

第一行一个正整数 $n$，表示楼房数量。

随后一行 $n$ 个正整数，第 $i$ 个为编号为 $i$ 的楼房的高度。

输出格式

输出一行一个整数表示能拍出的不同的美丽的照片数量。

10
2 2 1 1 2 2 3 1 3 3 

8

提示

本题采用捆绑测试。你只有通过 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$ 位有符号整数的范围。

本题输入数据量较大，请使用较快的读入方式。