Capital of hills

[1vf9z8AR]

Question-
Sunderland capital consists of n hills, forming a straight line. On each hill there was a watchman, who watched the neighbourhood day and night.

In case of any danger the watchman could make a fire on the hill. One watchman could see the signal of another watchman, if on the straight line connecting the two hills there was no hill higher than any of the two. For example, for any two neighbouring watchmen it is true that the signal of one will be seen by the other.

An important characteristics of this watch system was the amount of pairs of watchmen able to see each other's signals. You are to find this amount by the given heights of the hills.

Input

The first line of the input data contains an integer number n (3 ≤ n ≤ 106), n — the amount of hills in the capital. The second line contains n numbers — heights of the hills. All height numbers are integer and lie between 1 and 109.

Output

Print the required amount of pairs.

Constraints

3 ≤ n ≤ 106

All height numbers are integer and lie between 1 and 109

SAMPLE INPUT
4
2 3 2 1
SAMPLE OUTPUT
3
Explanation
Required Pairs are (1,2), (2,3) and (3,4) hence output is 3.

Issue-
Wrong answer.

My logic-
Find next greater and previous greater element for each element.

For each parent element run from element to next greater and if any element in between has previous greater in front of parent element break loop.

Add 1 to ans for each iteration

  #include<iostream>
#include<stack>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    stack<int>s;
    int ng[n],pg[n];
    for(int i=0;i<n;i++)
    {
        if(s.empty())
        {
            s.push(i);
            continue;
        }
        while(!s.empty() && arr[i]>arr[s.top()])
        {
            ng[s.top()]=i;
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty())
    {
        ng[s.top()]=-1;
        s.pop();
    }
    for(int i=n-1;i>=0;i--)
    {
        if(s.empty())
        {
            s.push(i);
            continue;
        }
        while(!s.empty() && arr[i]>arr[s.top()])
        {
            pg[s.top()]=i;
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty())
    {
        pg[s.top()]=-1;
        s.pop();
    }
    long long int ans=0;
    for(int i=0;i<n-1;i++)
    {
        int lim=ng[i];
        ans++;
        if(lim==-1)
        {
            for(int j=i+2;j<n;j++)
            {
                if(pg[j]>i)
                    break;
                else
                    ans++;
            }
        }
        else
        {
            for(int j=i+2;j<=lim;j++)
            {
                cout<<i<<" "<<j<<endl;
                if(pg[j]>i)
                    break;
                else
                    ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

[keskiverto]

One watchman could see the signal of another watchman, if on the straight line connecting the two hills there was no hill higher than any of the two.

A pair is valid, IF
max(hills in between) <= min(pair)

A B C D
3 2 1 3

The trivial pairs are: AB, BC, CD
AD and BD are also pairs? Answer should thus be '5'?

Your output:

1 3
4

Two lines, three numbers.

[ne555]

> 3 ≤ n ≤ 106
going to guess that the upper limit should be 1000000

> if any element in between has previous greater in front of parent element break loop.
¿why break? keskiverto gived you a counterexample
the problem is that if you go to your ng you may have exceed the time limit


by the way, I think that some elements of `ng' and `pg' may remain uninitialised.

[Enoizat]

ne555 wrote:

going to guess that the upper limit should be 1000000

Bingo, ne555. The original text is here:
https://www.hackerearth.com/practice/data-structures/stacks/basics-of-stacks/practice-problems/algorithm/capital-of-hills/
When the OP writes 106 it should be read 10^6 and 109 should be 10^9.