DELARRAY editorial(unofficial) - LUNCHTIME74

[kshitij_789]

O(N) solution
(code is according to 1 indexing 1…N)

left is length of longest prefix strictly increasing sequence
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.

[kshitij_789]

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

think a little bit you will get it

[sorb1997]

Yup nice observation. Didn’t realise it.

[betuyash]

Thanks verma_ankit484 .I didn’t know this method before , but your post helped me to learn new advance technique

[ssrivastava990]

Thank you so so much bro for explaining by using example
I m very thankful to you that finally i understands the solution in best way (yaa i take some time to understand the soln) but instead of just ignore the problem i finally understands.
Thanks Buddy

[ravikant88]

Happy to help