F. Образуйте треугольники
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ палочек, пронумерованных от $$$1$$$ до $$$n$$$. Длина $$$i$$$-й палочки равна $$$a_i$$$.

Вам нужно ответить на $$$q$$$ запросов. В каждом запросе вам даны два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$, $$$r - l + 1 \ge 6$$$). Определите, можно ли из палочек с номерами от $$$l$$$ до $$$r$$$ выбрать $$$6$$$ различных палочек, чтобы они образовали $$$2$$$ невырожденных треугольника$$$^{\text{∗}}$$$.

$$$^{\text{∗}}$$$Треугольник с длинами сторон $$$a$$$, $$$b$$$ и $$$c$$$ называется невырожденным, если:

  • $$$a < b + c$$$,
  • $$$b < a + c$$$, и
  • $$$c < a + b$$$.
Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$6 \le n \le 10^5$$$, $$$1 \le q \le 10^5$$$) — количество палочек и количество запросов соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — $$$a_i$$$ обозначает длину $$$i$$$-й палочки.

Каждая из следующих строк $$$q$$$ содержит по два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$, $$$r - l + 1 \ge 6$$$) — параметры запроса.

Выходные данные

Для каждого запроса выведите «YES» (без кавычек), если можно сформировать $$$2$$$ треугольника, и «NO» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
10 5
5 2 2 10 4 10 6 1 5 3
1 6
2 7
2 8
5 10
4 10
Выходные данные
YES
NO
YES
NO
YES
Примечание

В первом запросе длины палочек равны $$$[5, 2, 2, 10, 4, 10]$$$. Два набора палочек $$$[2, 4, 5]$$$ и $$$[2, 10, 10]$$$ могут быть выбраны для образования $$$2$$$ невырожденных треугольников.

Во втором запросе длины палочек равны $$$[2, 2, 10, 4, 10, 6]$$$. Можно показать, что невозможно образовать $$$2$$$ невырожденных треугольника.

В третьем запросе длины палочек равны $$$[2, 2, 10, 4, 10, 6, 1]$$$. Можно выбрать два набора палочек $$$[1, 2, 2]$$$ и $$$[4, 10, 10]$$$, чтобы образовать $$$2$$$ невырожденных треугольника.

В четвертом запросе длины палочек равны $$$[4, 10, 6, 1, 5, 3]$$$. Можно показать, что невозможно образовать $$$2$$$ невырожденных треугольника.

В пятом запросе длины палочек равны $$$[10, 4, 10, 6, 1, 5, 3]$$$. Можно выбрать два набора палочек $$$[1, 10, 10]$$$ и $$$[3, 4, 5]$$$, чтобы образовать $$$2$$$ невырожденных треугольника.