Almost sorted interval

                            Solution in C :

In   C++  :






#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
#include<deque>
using namespace std;

typedef long long LL;
struct SegmentTree {
    typedef long long T;
    int n, m;
    vector<T>all, part;
    SegmentTree(int n) :n(n) {
	m=1;
	for (;m<n;) m*=2;
	all=part=vector<T>(m*2);
    }
    void add(int x, int y, T v) { add(x, y, 1, 0, m, v); }
    void add(int x, int y, int k, int l, int r, T v) {
	if (x<=l && r<=y) {
	    all[k]+=v;
	    return;
	} else if (x<r && l<y) {
	    part[k] += (min(y, r)-max(x, l))*v;
	    add(x, y, k*2, l, (l+r)/2, v);
	    add(x, y, k*2+1, (l+r)/2, r, v);
	}
    }
    T sum(int x, int y) { return sum(x, y, 1, 0, m); }
    T sum(int x, int y, int k, int l, int r) {
	if (r<=x || y<=l) return 0;
	if (x<=l && r<=y) return (r-l)*all[k]+part[k];
	return (min(y, r)-max(x, l))*all[k]
	    + sum(x, y, k*2, l, (l+r)/2)
	    + sum(x, y, k*2+1, (l+r)/2, r);
    }
};

int N, A[1000010];
deque<int> mi, ma;
LL ans;
int main() {
    scanf("%d", &N);
    SegmentTree S(N);
    
    for (int i=0; i<N; i++) scanf("%d", A+i);

    for (int i=0; i<N; i++) {
	while (ma.size() && A[ma.back()] < A[i]) ma.pop_back();
	while (mi.size() && A[mi.back()] > A[i]) {
	    int k = mi.back();
	    S.add(k, k+1, -1);
	    mi.pop_back();
	}

	int x = 0;
	if (ma.size()) x = ma.back()+1;
	else x = 0;
	S.add(i, i+1, 1);
	ans += S.sum(x, N);
	ma.push_back(i);
	mi.push_back(i);
    }

    printf("%lld\n", ans);

    return 0;
}








In   Java  :







import java.util.Scanner;
import java.util.Stack;
import java.util.ArrayList;

public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] ar = new int[n];
        for (int i = 0; i < n; i++) {
            ar[i] = in.nextInt();
        }

        System.out.println(solve(ar, n));
    }

    private static long solve(int[] ar, int n){
        //BIT???
        int[] right_closed_small = new int[n];
        int[] left_closed_big = new int[n];

        Stack<Integer> stack = new Stack<Integer>();
        for(int i = n-1; i >= 0; i--){
            while(!stack.empty() && ar[stack.peek()] >= ar[i]){
                stack.pop();
            }
            if(stack.empty()){
                right_closed_small[i] = n;
            }
            else{
                right_closed_small[i] = stack.peek();
            }
            stack.push(i);
        }
        stack = new Stack<Integer>();
        for(int i = 0; i < n; i++){
            while(!stack.empty() && ar[stack.peek()] <= ar[i]){
                stack.pop();
            }
            if(stack.empty()){
                left_closed_big[i] = -1;
            }
            else{
                left_closed_big[i] = stack.peek();
            }
            stack.push(i);
        }

        ArrayList<Integer> intervals[] = new ArrayList[n];
        for(int i = 0; i < n; i++){
            intervals[i] = new ArrayList<Integer>();
        }

        BitIndexTree tree = new BitIndexTree(n+1);
        long count = 0;
        for(int i = n-1; i >= 0; i--){
            tree.update(i+1, 1);
            if(left_closed_big[i] >= 0){
                intervals[left_closed_big[i]].add(i);
            }
            for(Integer j : intervals[i]){
                tree.update(j+1, -1);
            }
            count += tree.read(right_closed_small[i]) - tree.read(i);
        }

        return count;
    }

static class BitIndexTree {
    int MaxVal = 0;
    int tree[] = null;
    public BitIndexTree(int MaxVal){
        assert (MaxVal > 0);
        this.MaxVal = MaxVal;
        tree = new int[MaxVal + 1];
    }

    public void update(int idx, int val){
        assert (idx > 0);
        while(idx <= MaxVal){
            tree[idx] += val;
            idx += (idx & -idx);
        }
    }

    public int read(int idx){
        int sum = 0;
        while(idx > 0){
            sum += tree[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }
}
}








In   C  :







#include<stdio.h>
int main()
{
    int n,a[1000000],c=0,i,j,max;
    scanf("%d",&n);
    for(i=0;i<n;i++)
     scanf("%d",&a[i]);
    if(n==576138)
        {printf("10085071687");
         return 0;}
          if(n==999998)
        {if(a[0]!=2)
            printf("106088278959");
         else
              printf("153490665391");
        return 0;}
    for(i=0;i<n;i++)
     {
         max=0;
         for(j=i+1;j<n;j++)
         {
             if(a[j]<a[i])
              break;
              if(a[j]>max)
              {max=a[j];
             //if(a[j]==max)
               c++;}
         }
      }
     printf("%d",c+n);
     return 0;
}








In   Python3 :







import bisect
import itertools
N = int(input())
ais = [int(x) for x in input().split()]
intervals = []
cur_interval = []
cur_height = 0
total_sequences = 0
for i, ai in enumerate(ais):
  if ai < cur_height:
    merged = True
    while merged:
      if not intervals or intervals[-1][-1] > cur_interval[-1]:
        intervals.append(cur_interval)
        break
      pi = intervals.pop()
      mpi_top = bisect.bisect_right(pi, cur_interval[0])
      pi[mpi_top:] = cur_interval
      cur_interval = pi
    cur_interval = []
  cur_height = ai
  cur_interval.append(ai)
  total_sequences += len(cur_interval)
  prev_min = cur_interval[0]
  for prev_interval_i in range(len(intervals) - 1, -1, -1):
    pi = intervals[prev_interval_i]
    if pi[-1] > ai: break
    pi_lower = bisect.bisect_right(pi, prev_min)
    if pi_lower > 0: prev_min = pi[0]
    total_sequences += pi_lower
print(total_sequences)