F. Triangle Formation
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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{∗}}$$$.

$$$^{\text{∗}}$$$A triangle with side lengths $$$a$$$, $$$b$$$, and $$$c$$$ is called non-degenerate if:

  • $$$a < b + c$$$,
  • $$$b < a + c$$$, and
  • $$$c < a + b$$$.
Input

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

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.

Example
Input
10 5
5 2 2 10 4 10 6 1 5 3
1 6
2 7
2 8
5 10
4 10
Output
YES
NO
YES
NO
YES
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.