Problem can be simplified like these: Let's call pair $$$(i, j)$$$ bad if $$$i < j$$$ and $$$a_i > a_j$$$. We need to find if maximum sum of bad pars, which is inside $$$[l_i, r_i]$$$, is not greater than $$$k$$$ (for all bad $$$(i, j)$$$ satisfies $$$a_i + a_j \le k$$$).

Create a segment tree for maximum value and a merge sort tree where each node has a sorted vector containing all elements in the range of this node. Store the maximum sum of bad pair, which is inside $$$[l_{node},r_{node}]$$$, in $$$vis_{node}$$$. Now we can answer the query recursively like a segment tree. For some $$$node$$$ if $$$[l_{node},r_{node}]$$$ is outside $$$[l_i, r_i]$$$ its answer is $$$true$$$. If its entirely contained, first we check if $$$vis_{node} \le k$$$, if so we can do binary search on the vector to find the greatest element which is smaller than $$$mx$$$ (max number before this segment($$$node$$$)) to find maximum sum of bad pairs which right element is in $$$[l_{node},r_{node}]$$$ and left element is in $$$[l_i, l_{node} - 1]$$$. And check $$$mx + element \le k$$$ then update $$$mx$$$. If neither of the previous conditions are satisfied, we take the answer of the left child and the answer of the right child. Check if they are both $$$true$$$. Time complexity for building the merge sort tree is $$$O(nlogn)$$$ because we go through each element $$$logn$$$ times, and the time complexity for answering the queries is $$$O(qlog^2n)$$$ because in each query we visit logn nodes at most, doing binary search in each one in $$$O(logn)$$$.

Not VPN, TOR browser with bridge.