Oasis Reunion

Time limit1sMemory limit256 MB

Summary
Given a line of heights, count pairs who can mutually see each other using a monotonic stack while handling equal-height ties correctly.
Level

Medium6 of 10

Topics
Stack, Array
Solved
No attempts yet

Problem

N people are standing in one line to watch an Oasis reunion concert.

Two people A and B can see each other if every person standing between them is no taller than the shorter of A and B. People of the same height do not block each other's view.

Given the people's heights in line order, count the number of pairs of people who can see each other.

Input

The first line contains the number of people N. (1 <= N <= 500,000)

Each of the next N lines contains one person's height in nanometers, in line order. Every height is less than 2^31 nanometers.

Output

Print the number of pairs of people who can see each other.

Examples1

  1. Example 1

    Input
    7
2
4
1
2
2
5
1
    Expected output
    10