Split
Contest: Codeforces Round 905 (Div. 1)
Difficulty rating: 2700
Tags: binary search, data structures, divide and conquer, dsu, math, trees, two pointers

Let's call an array $$$b_1, b_2, \ldots, b_m$$$ ($$$m \ge 2$$$) good if it can be split into two parts such that all elements in the left part are strictly smaller than all elements in the right part. In other words, there must exist an index $$$1 \le i < m$$$ such that every element from $$$b_1, \ldots, b_i$$$ is strictly smaller than every element from $$$b_{i+1}, \ldots, b_m$$$.

Given an array $$$a_1, a_2, \ldots a_n$$$ consisting of distinct integers from $$$1$$$ to $$$n$$$. There are $$$q$$$ queries. Each query consists of two numbers $$$l$$$ and $$$r$$$. For each query, determine whether the array $$$a_l, a_{l+1}, \ldots, a_r$$$ is good.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the size of the array.

The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_n \le n$$$) — the elements of the array $$$a$$$.

The third line contains a single integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i < r_i \le n$$$) — the description of the $$$i$$$-th query.

Output format:
For each query, output "Yes" (without quotes) if the array $$$a_l, a_{l+1}, \ldots, a_r$$$ is good, and "No" (without quotes) otherwise.

You can output "Yes" and "No" in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example:

- The array $$$[3,2,1,4,5]$$$ can be split into two parts: $$$[3,2,1]$$$ and $$$[4,5]$$$.
- The array $$$[3,2,1]$$$ cannot be split into two parts such that all elements in the left part are smaller than all elements in the right part.
- The array $$$[3,2,1,4]$$$ can be split into two parts: $$$[3,2,1]$$$ and $$$[4]$$$.
- The array $$$[3,2]$$$ cannot be split into two parts such that all elements in the left part are smaller than all elements in the right part.
- The array $$$[2,1,4,5]$$$ can be split into two parts: $$$[2,1]$$$ and $$$[4,5]$$$.

In the second example:

- The array $$$[2,4,3]$$$ can be split into two parts: $$$[2]$$$ and $$$[4,3]$$$.
- The array $$$[6,2,4,3,5]$$$ cannot be split into two parts such that all elements in the left part are smaller than all elements in the right part.
- The array $$$[4,3,5]$$$ can be split into two parts: $$$[4,3]$$$ and $$$[5]$$$.

Example input:
5
3 2 1 4 5
5
1 5
1 3
1 4
1 2
2 5

Example output:
Yes
No
Yes
No
Yes

Example input:
6
1 6 2 4 3 5
3
3 5
2 6
4 6

Example output:
Yes
No
Yes

Editorial:
Let's fix element $$$i$$$. Let's find all intervals $$$[l, r]$$$ for which this element can be the maximum in the left part of a valid cut. Let $$$x_l$$$ be the nearest element to the left of $$$i$$$ greater than $$$a_i$$$, and $$$x_r$$$ be the nearest element to the right of $$$i$$$ greater than $$$a_i$$$. Then, for $$$i$$$ to be the maximum element in the left part of the cut, the following conditions must be satisfied: $$$$$$ \begin{cases} x_l < l \le i\\ x_r \le r \end{cases} $$$$$$
But these conditions are obviously not enough, as we need to guarantee that all elements in the right part of the cut are greater than all elements in the left part of the cut. However, since $$$i$$$ is the maximum element in the left part of the cut, it is sufficient for all elements in the right part of the cut to be greater than $$$a_i$$$. Therefore, if $$$y_r$$$ is the nearest element to the right of $$$x_r$$$ smaller than $$$a_i$$$, then $$$r \le y_r$$$.
Thus, element $$$i$$$ can be the maximum element in the left part of the cut of interval $$$[l, r]$$$ $$$\Longleftrightarrow$$$ the following conditions are satisfied: $$$$$$ \begin{cases} x_l < l \le i\\ x_r \le r < y \end{cases} $$$$$$
For each element $$$i$$$, we can find $$$x_l$$$, $$$x_r$$$, and $$$y$$$ in $$$\mathcal{O}(\log n)$$$ time. This can be done, for example, using a segment tree or std::set if the elements are iterated in ascending order.
It only remains to notice that if we consider the queries $$$[l, r]$$$ as points $$$(l, r)$$$, then each element $$$i$$$ makes all points in some rectangle good. Thus, the problem reduces to checking whether a point lies in one of the rectangles. This is a classic problem that can be solved using sweep line and, for example, a segment tree. We obtained a solution with a time complexity of $$$\mathcal{O}(n\log n)$$$.