Background

There is no background.

Description

给定数列 \( a \)，定义一个有序数对 \(\left(i, j\right)\left(j > i\right)\) 是合法的，当且仅当

\[\min(a_i, a_j) \geq \max\limits_{k = i + 1}^{j - 1}a_k\]

若 \(j − i = 1\)，则默认合法。求该数列中合法数对的个数。

Format

Input

第一行一个整数 \(n\)，表示数列长度。

第二行 \(n\) 个整数，描述数列 \(a\)。

Output

一行表示合法数对个数。

Sample 1

Input

5
1 4 2 3 5

Output

6

Limitation

1s, 1024KiB for each test case.

Hint

Source

2021-9-20 contest