Given an array of $$$n$$$ integers, with $$$1 \le a_i \le 10^6$$$, and given queries of type $$$(l, r)$$$, find whether, if we delete all the elements of the array such that $$$l \le a_i \le r$$$, the resultant array will form a non-decreasing sequence. We need to answer these queries in $$$O(1)$$$ time complexity.
How to do this problem?








count number of inversions from these elements (including inversions going in the reverse direction)
range query and sum and if its equal to total inversions then yes else no
"range query and sum and if its equal to total inversions then yes else no"
I did not understand this line. Could you please elaborate it.
Can u provide us the question link
Can you explain in more detail. I am not able to understand it clearly. Thanks in advance
It was wrong
Create an array p that
p[i]={a[i],i}and sort it ascending.Find
Lwhich is the farthest position from the left where the sequence fromp[1].secondtop[L].secondis ascending, andRwhich is the farthest position from the right where the sequence fromp[R].secondtop[n].secondis ascending.Which each query
l,r, it's possible ifl<=p[L].first && r>=p[R].firstand vise versa.