Aladdin has to fly his carpet in order to reach to Jasmine.
He can only move in a straight line horizontally and not up or down.
There are ‘N’ buildings in a row from left to right.
He can travel successfully from building i to building j (i ≠ j)
Only if the height(i)=height(j) and the heights of all the buildings between i and j is strictly less or equal to the height(i).
Help Aladdin to find such number of valid paths represented by ordered pairs.
The first line contains N , the number of buildings.
The next line contains N space separated integers ,each denoting the height of each building.
Print an integer that denotes the number of valid paths.
1 <= N <= 3.10^5
Height(building) < 10^6
3 2 1 2 3 3
Buildings with indices (1, 5), (1, 6) (5, 6) and (2, 4) and the paths in the opposite directions are the only valid paths.
Test Case 1: link
Test Case 2: link
PS: Use HackerEarth api to compile large inputs
Kunal Desai : 7715051136
Neelraj Patil : 9930671144