Rooftop Garden Benchmarking

Interview

Time limit1sMemory limit128 MB

Summary

Count, over every building, how many strictly shorter buildings stand to its right before a building at least as tall blocks the view.

Level: Medium7 of 10
Topics: Stack, Array, Implementation, Greedy
Solved: No attempts yet

Problem

Rooftop garden

There are $N$ buildings standing in a row in a city. The $i$ -th building from the left has height $h_i$ .

Every building manager is diligent and wants to benchmark the rooftop gardens of other buildings. Each manager can look only to the right from their own building, so manager $i$ initially wants to see the rooftops of buildings $i+1, i+2, \dots, N$ .

The view can be blocked, however. Looking to the right, the moment a manager meets a building whose height is greater than or equal to their own, that building and every building beyond it become invisible. In other words, manager $i$ can only see a consecutive run of strictly shorter buildings, and the view is blocked as soon as the first building of height at least $h_i$ appears (that blocking building is not counted either).

Find the total number of rooftop gardens that all managers can benchmark.

For example, consider $N = 6$ with heights $H = \{10, 3, 7, 4, 12, 2\}$ , illustrated below.

             = 
 =           = 
 =     -     = 
 =     =     =        -> viewing direction
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> building heights
[1][2][3][4][5][6]    -> building numbers

Manager 1 (height 10) sees buildings 2, 3, and 4, but building 5 (height 12) is at least as tall, so the view stops there. → 3
Manager 2 (height 3) is blocked immediately by building 3 (height 7). → 0
Manager 3 (height 7) sees only building 4 and is blocked by building 5 (height 12). → 1
Manager 4 (height 4) is blocked immediately by building 5 (height 12). → 0
Manager 5 (height 12) sees only building 6. → 1
Manager 6 is the last building and has nothing to look at. → 0

Therefore the total is $3 + 0 + 1 + 0 + 1 + 0 = 5$ .

Input

The first line contains the number of buildings $N$ . ( $1 \le N \le 80000$ )
Each of the next $N$ lines contains one building height $h_i$ . ( $1 \le h_i \le 10^9$ )

Output

Print, on a single line, the total number of rooftop gardens (buildings) that all managers can benchmark.

Examples4

Example 1
Input
```
6
10
3
7
4
12
2
```
Expected output
```
5
```
Example 2
Input
```
1
5
```
Expected output
```
0
```
Example 3
Input
```
5
1
2
3
4
5
```
Expected output
```
0
```
Example 4
Input
```
5
5
4
3
2
1
```
Expected output
```
10
```