9.2 Aladdin

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.
Input Format
The first line contains N , the number of buildings.
The next line contains N space separated integers ,each denoting the height of each building.
Output Format
Print an integer that denotes the number of valid paths.
Constraints
1 <= N <= 3.10^5
Height(building) < 10^6
Sample Input
6
3 2 1 2 3 3
Sample Output
8
Explanation
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 Cases
Test Case 1: link
Test Case 2: link

PS: Use HackerEarth api to compile large inputs

This challenge is worth 80 points.

You must be logged in to submit a solution

Contact Us

Kunal Desai : 7715051136

Neelraj Patil : 9930671144