Daft Trunk are ready to move onto the next phase of producing their album: sampling!

They are going through hours of random music recordings. The recording is represented as an array of ~n~ integers denoting pitch values. To create peak, they want to slice out a contiguous subarray (a sequence of consecutive elements) from the recording to use as a loop. However, a loop is only usable if it represents a valid sawtooth wave.

Formally, an array ~a~ is a valid sawtooth wave if there is no index ~i~ ~(3 \le i \le n)~ such that ~a_{i-2} > a_{i-1} > a_i~ (~1~-indexed).

Given the recording of ~n~ pitches, what is the total number of valid sawtooth wave subarrays?

Input

The first line contains a single integer ~n~ ~(1 \le n \le 2 \times 10^5)~, the size of the studio recording.

The second line contains ~n~ integers ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~, the recorded pitch values.

Output

Output a single integer, the total number of contiguous subarrays that are valid sawtooth waves.

Example

Input 1

3
3 2 1

Output 1

5

Explanation: The entire array of [3,2,1] is invalid because ~3~ > ~2~ > ~1~. However, all the other subarrays are valid: [3], [2], [1], [3, 2], and [2, 1].

Therefore, the answer is ~5~.

Input 2

3
1 1 1

Output 2

6