Triangle Formation
Contest: Pinely Round 4 (Div. 1 + Div. 2)
Difficulty rating: 2200
Tags: brute force, greedy, implementation, math, sortings

You are given $$$n$$$ sticks, numbered from $$$1$$$ to $$$n$$$. The length of the $$$i$$$-th stick is $$$a_i$$$.

You need to answer $$$q$$$ queries. In each query, you are given two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$, $$$r - l + 1 \ge 6$$$). Determine whether it is possible to choose $$$6$$$ distinct sticks from the sticks numbered $$$l$$$ to $$$r$$$, to form $$$2$$$ non-degenerate triangles$$$^{\text{∗}}$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$6 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$) — the number of sticks and the number of queries respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — $$$a_i$$$ denotes the length of the $$$i$$$-th stick.

Each of the following $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$, $$$r - l + 1 \ge 6$$$) — the parameters of each query.

Output format:
For each query, output "YES" (without quotes) if it is possible to form $$$2$$$ triangles, and "NO" (without quotes) otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

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

Note:
In the first query, the lengths of the sticks are $$$[5, 2, 2, 10, 4, 10]$$$. Two sets of sticks $$$[2, 4, 5]$$$ and $$$[2, 10, 10]$$$ can be selected to form $$$2$$$ non-degenerate triangles.

In the second query, the lengths of the sticks are $$$[2, 2, 10, 4, 10, 6]$$$. It can be shown that it is impossible to form $$$2$$$ non-degenerate triangles.

In the third query, the lengths of the sticks are $$$[2, 2, 10, 4, 10, 6, 1]$$$. Two sets of sticks $$$[1, 2, 2]$$$ and $$$[4, 10, 10]$$$ can be selected to form $$$2$$$ non-degenerate triangles.

In the fourth query, the lengths of the sticks are $$$[4, 10, 6, 1, 5, 3]$$$. It can be shown that it is impossible to form $$$2$$$ non-degenerate triangles.

In the fifth query, the lengths of the sticks are $$$[10, 4, 10, 6, 1, 5, 3]$$$. Two sets of sticks $$$[1, 10, 10]$$$ and $$$[3, 4, 5]$$$ can be selected to form $$$2$$$ non-degenerate triangles.

Example input:
10 5
5 2 2 10 4 10 6 1 5 3
1 6
2 7
2 8
5 10
4 10

Example output:
YES
NO
YES
NO
YES

Editorial:
Hint 1
Under the constraints of the problem, there exists a (small) integer $$$C$$$ such that for intervals longer than $$$C$$$, it is guaranteed to form two triangles.
Solution
If there are at least $$$45$$$ sticks, it is guaranteed to form a triangle. Proof: For any sequence of stick lengths that cannot form a triangle, we can replace it with the Fibonacci sequence. By replacing the sticks in increasing order, the sequence will remain incapable of forming a triangle. This implies that the Fibonacci sequence is one of the longest sequences that cannot form a triangle. The $$$45$$$th Fibonacci number exceeds $$$10^9$$$. Therefore, having at least $$$45$$$ sticks ensures that it is possible to form a triangle.
If there are at least $$$48$$$ sticks, it is guaranteed to form two triangles. Proof: We can first form the first triangle and remove those sticks. The remaining number of sticks is still at least $$$45$$$, which is sufficient to form the second triangle.
Therefore, only for intervals with fewer than $$$48$$$ sticks, we need to check whether it is possible to form two triangles.
First, we sort the sticks within the interval. Then we use the following algorithm to find two triangles:
Algorithm 1: Enumerate all possible sets of $$$6$$$ consecutive sticks and check if they can form two triangles.
Algorithm 2: Identify all possible sets of $$$3$$$ consecutive sticks that can form a triangle, and check if there exist two disjoint sets among them.
If neither algorithm can find two triangles, then it is impossible to form two triangles within the given interval. Proof: Consider an interval where Algorithm 1 cannot find two triangles. Suppose it is indeed possible to form two triangles; the six sticks must be non-consecutive. For any unselected sticks between the chosen sticks, if there exists a stick to its left and a stick to its right that belongs to the same triangle, we can replace the rightmost stick of this triangle with the unselected stick. Continuing this process, either the six sticks will become consecutive, or the left side will form one triangle and the right side will form another, which can be detected by Algorithm 2.