#
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

View ranklist for this challenge

About scoring and submission