using namespace std;

typedef long long ll;

const int MAXN = 1001000; int fenwickTree[MAXN], n; vector addLater[MAXN];

inline int getPrefixSum(int idx) { int sum = 0; while (idx >= 0) { sum += fenwickTree[idx]; idx = (idx & (idx + 1)) - 1; } return sum; }

inline void update(int idx, int delta) { while (idx < n) { fenwickTree[idx] += delta; idx = (idx | (idx + 1)); } }

ll solve(vector& arr) { vector nextGreater(sz(arr)), prevSmaller(sz(arr)); vector st;

// Calculate previous smaller elements
for (int i = sz(arr) - 1; i >= 0; --i) {
    while (!st.empty() && arr[st.back()] >= arr[i])
        st.pop_back();
    prevSmaller[i] = st.empty() ? -1 : st.back();
    st.push_back(i);
}

// Clear stack for next greater elements
st.clear();

// Calculate next greater elements
forn(i, sz(arr)) {
    while (!st.empty() && arr[st.back()] <= arr[i])
        st.pop_back();
    nextGreater[i] = st.empty() ? sz(arr) : st.back();
    st.push_back(i);
}

// Prepare for updates
forn(i, sz(prevSmaller)) {
    if (prevSmaller[i] != -1)
        addLater[prevSmaller[i] + 1].push_back(i);
}

ll result = 0;
forn(i, sz(arr)) {
    for (int idx : addLater[i])
        update(idx, 1);
    if (nextGreater[i] != sz(arr))
        result += getPrefixSum(nextGreater[i] - 1) - getPrefixSum(i - 1);
}

return result;

}

int main() { n = readInt(1, MAXN); vector arr(n); forn(i, n) { arr[i] = readInt(1, n) - 1; } cout << solve(arr) << endl; return 0; }

Python3 solution

import sys

def permute(l):
    l = l[:1] + l[:]
    n = len(l)
    nn = n + 12
    left = [0] * n
    right = [n] * n
    stack = left[:]
    arr = [0] * (nn)
    r = [[] for _ in range(n)]  # create 2d list with deep copy
    # after testcase 6 find left[],right[] take a round 3s
    top = 0
    for i in range(1, n):
        val = l[i]
        while top > 0 and val > l[stack[top - 1]]:
            top -= 1
        if top:
            left[i] = stack[top - 1]
        stack[top] = i
        top += 1
    top = 0
    for i in range(n - 1, 0, -1):
        val = l[i]
        while top > 0 and val < l[stack[top - 1]]:
            top -= 1
        if top:
            right[i] = stack[top - 1]
        stack[top] = i
        top += 1
    # big neck bottle
    ans = 0
    for i in range(n - 1, 0, -1):
        for j in r[i]:
            while j <= nn:
                arr[j] += -1
                j += (j & (-j))
        j = i
        while j <= nn:
            arr[j] += 1
            j += (j & (-j))
        r[left[i]].append(i)
        v = 0
        x = right[i] - 1
        while x > 0:
            v += arr[x]
            x -= (x & (-x))
        ans += v
    return ans

if __name__ == '__main__':
    n = sys.stdin.readline().split()
    l = tuple(map(int, sys.stdin.readline().split()))
    print(permute(l))

Hi Not sure who may look It looks like test expected output is wrong for several input test cases (I manually calculated periods for some and never got as expected output)

Moreover, then I looked at Editorial section and seems there is an error That code gives 17 count for input: 7, {3, 1, 2, 5, 4, 6, 7} Will not be there only 13: {3}, {1}, {1, 2}, {1, 2, 5}, {2}, {2, 5}, {5}, {4}, {4, 6}, {4, 6, 7}, {6}, {6, 7}, {7}?

Hi, I have written code in Ruby. It works fine in my local but here it says wrong answer for test case 4

        def solve(arr)
        count = 0
        arr.each_with_index do |a,i|
        count +=1 
        j = i+1
        while j <= arr.length - 1
break if arr[j] < a
if arr[j] > arr[j-1] && arr[j] > a
  count = count + 1 

  j = j + 1
elsif arr[j] < arr[j-1]
next_big_elem = arr[j..arr.length - 1].select{|x| x if x>arr[j-1]}.first

    if next_big_elem
      count = count + 1 
      j = arr.index(next_big_elem)+1
    end
    break
            end
            end
            end
            print count
            count
end

end

here is hackerrank almost sorted interval solution