First off, some definitions.
An array of length at least 2 having distinct integers is said to be fantabulous iff the second highest element lies strictly to the left of the highest value. For example, [1, 2, 13, 10, 15] is fantabulous as the second-highest value 13 lies to the left of highest value 15.
For every fantabulous array, we define a fantabulous pair (a, b) where a denotes the index of the second-highest value (1-indexed) and b denotes the index of the highest value (1-indexed). In the above array, the fantabulous pair is (3, 5).
Mancunian challenges you to solve the following problem. Given an array, find the total number of distinct fantabulous pairs over all its subarrays.
Input:
The first line contains an integer N denoting the length of the array. The next line contains N distinct integers denoting the elements of the array.
Output:
Output a single integer which is the answer to the problem.
Constraints:
1 <= N <= 106
1 <= array elements <= 109
Array elements are distinct.
Let us consider all the subarrays of the given array.
The subarray [1] is not fantabulous.
The subarray [2] is not fantabulous.
The subarray [3] is not fantabulous.
The subarray [4] is not fantabulous.
The fantabulous pair for subarray [1, 3] is (1, 2).
The subarray [3, 2] is not fantabulous.
The fantabulous pair for subarray [2, 4] is (1, 2).
The subarray [1, 3, 2] is not fantabulous.
The fantabulous pair for subarray [3, 2, 4] is (1, 3).
The fantabulous pair for subarray [1, 3, 2, 4] is (2, 4).
So, there are the 3 distinct pairs, which are (1, 2), (1, 3) and (2, 4).
