Jim and the Skyscrapers

                            Solution in C :

In C ++  :







#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int NMAX = 300010, CMAX = 1000010;

int N, V[NMAX], Right[NMAX];
stack<int> S;
vector<int> Val[CMAX];
long long Ans;

int main()
{
  //  freopen("c.in", "r", stdin);
   // freopen("c.out", "w", stdout);

    scanf("%i", &N);
    for(int i = 1; i <= N; ++ i)
    {
        scanf("%i", &V[i]);
        Val[V[i]].push_back(i);
    }

    V[N + 1] = CMAX;

    S.push(N + 1);
    for(int i = N; i; -- i)
    {
        while(!S.empty() && V[S.top()] <= V[i]) S.pop();
        Right[i] = S.top();
        S.push(i);
    }

    for(int i = CMAX - 1; i >= 1; -- i)
    {
        int Ptr = 0;
        for(int j = 0; j < Val[i].size(); )
        {
            while(Ptr < Val[i].size() && Val[i][Ptr] <= Right[ Val[i][j] ]) Ptr ++;
            int Len = Ptr - j;
            Ans += 1LL * Len * (Len - 1);
            j = Ptr;
        }
    }

    printf("%lld", Ans);
}









In Java :




import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
       
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        TreeMap<Integer,Integer> T=new TreeMap<Integer,Integer>();
        long output=0L;
        for (int i=0;i<n;i++){
            int val=in.nextInt();
            //add this new val to T
            if (T.get(val)==null){T.put(val,1);}
            else {
                int num=T.get(val);
                T.put(val,num+1);
            }
            //kill old values smaller than this new val
            while (T.lowerKey(val)!=null){
                int k=T.lowerKey(val);
                //add to output
                int thisNum=T.get(k);
                output+=thisNum*(thisNum-1);
                //remove
                T.remove(k);
            }
        }
        //finisher
        for (int k:T.keySet()){
            //add to output
            long thisNum=(long)T.get(k);
            output+=thisNum*(thisNum-1);
            
        }
        
        System.out.println(output);
        
    }
}








In C :





#include<stdio.h>
int main()
{
    int n,t,i,j,a[300001],b[300001],c[1000002];//change
    long long d;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<=1000000;i++)
    {
        c[i]=0;
    }
    t=0;
    d=0;
    b[0]=a[0];
    c[a[0]]=1;
    for(i=1;i<n;i++)
    {
        if(a[i]>b[t])
        {
            while(a[i]>b[t]&&t>=0)
            {
                c[b[t]]=0;
                t--;
            }
            t++;
            b[t]=a[i];
            c[a[i]]++;
        }
        else
        {
            t++;
            b[t]=a[i];
            c[a[i]]++;
        }
        if(c[a[i]]!=0)
        {
            d+=c[a[i]]-1;
        }
    }
    printf("%lld",2*d);
    return 0;
}









In Python3 :





N = int(input())
h = [int(i) for i in input().split()]

count = 0

s = []
for i in range(0,N):
    while len(s) > 0 and s[-1][0] < h[i]:
        s.pop()
    if len(s) > 0 and s[-1][0] == h[i]:
        count += s[-1][1]
        s[-1][1] += 1
    else:
        s.append([h[i],1])
    
print(2*count)