DELARRAY EDITORIAL(O(N) complexity unofficial)

1

Problem link- DELARRAY Problem - CodeChef

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-CodeChef: Practical coding for everyone