Problem link- codechef.com/problems/DELARRAY

O(N) solution

(code is according to 1 indexing 1…N)

let left be length of longest prefix strictly increasing sequence

let right is index of first element of longest suffix strictly increasing sequence

ans=0 l=left r=n while r>=right and l>0: if array[l]<=arr[r]: l-=1 else: ans+=l r-=1

ans+=left#(when removing subsequences which end at N) ans+=(n-right+1)#(when removing subsequences which start at 1) One corner case if left==N and right==1 then answer=(n*(n+1))/2-1 using combinatorics.

For more understanding

let a and b be the longest prefix and suffix interesting sequences.

Claim-If ith element of b is greater than 1st,2nd------------jth element of a then:-

(i+1)th element of b is greater than 1st,2nd----------kth element of a where k is greater than or equal to j

so start from last element and go leftwards in both arrays according to greater than or lesser than or equal to operators

solution link-https://www.codechef.com/viewsolution/25452707