Problem Description
There are N guard towers, with the ith guard tower from the left having height Hi. Two guard towers can see each other if no guard tower between them has a strictly greater height than both of the guard towers.
More specifically, guard towers i and j can see each other if there exists no k such that i < k < j and Hk > max(Hi, Hj).
Count the number of pairs of guard towers that can see each other. It is guaranteed that no two guard towers have the same height.
Input
The first line of input will contain one integer, N.
The next line of input will contain N integers, representing the array H.
Output
The output should contain one line with one integer, the number of pairs of guard towers that can see each other.
Limits
For all subtasks: 1 ≤ Hi ≤ 109.
Subtask 1 (18%): 1 ≤ N ≤ 300.
Subtask 2 (36%): 1 ≤ N ≤ 2000.
Subtask 3 (22%): 1 ≤ N ≤ 100000.
Subtask 4 (24%): 1 ≤ N ≤ 2000000.
Subtask 5 (0%): Sample Testcases.
Sample Input 1
5
1 5 2 3 6
Sample Output 1
8