从 地球上看到的夜空中有 N 颗星，这 N 颗星从东到西排成一条直线。从东数第 i 颗（1 \le i \le N）星是这些星中第 B_i 亮的星。

小Z决定按下述步骤拍摄夜空的照片：

1. 选择满足 1 \le l \le r \le N 的整数对 (l,r)，架设相机使东数第 l,l+1,\ldots,r 颗星全部收入取景框，且其他星不进入取景框。

2. 选择满足 1 \le b \le N 的整数 b，开放快门使 N 颗星中亮度排在第 1 到第 b 位（且位于取景框内）的星全部被拍到，而其他星不被拍到。

但是，不能拍出没有任何星星的照片。

求通过这种方式拍摄的夜空照片中，可能拍到的星星集合有多少种。

输入按以下格式给出：

N

B_1 B_2 ... B_N

输出答案。

样例1解释：

例如选择 (l,r)=(2,4), b=3，可以拍到东数第 2 颗和第 4 颗星这两颗星的照片。

包括这张照片在内，共可以拍到下面 12 种星星集合的照片。（每张照片中，更东边的星排列在更左边，第 i 亮的星上标着整数 i。）

除此之外的集合无法拍到，因此输出 12。

 1 \le N \le 5 \times 10^5

- 1 \le B_i \le N（1 \le i \le N）

- B_i \ne B_j（1 \le i < j \le N）

- 输入的所有值均为整数