Два отрезка: строго больше

4000 мс · 512 МБ · всё или ничего

То же, что в классной задаче N, но требуется, чтобы минимум на втором отрезке стал строго больше максимума на первом.

Формат ввода

В первой строке — числа $n$ и $q$ ( $1 \le n, q \le 10^5$ ). Во второй — $n$ чисел $A_i$ ( $1 \le A_i \le 10^9$ ). В следующих $q$ строках — четвёрки $l_1$ , $r_1$ , $l_2$ , $r_2$ ; отрезки не пересекаются.

Формат вывода

На каждый запрос выведите наименьшее число операций.

Примеры

ввод

6 4
3 5 2 3 10 11
1 2 3 4
1 3 4 6
1 4 5 6
4 5 1 2

вывод

ввод

2 1
1 1000000000
1 1 2 2

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.