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