D. LuoTianyi и функция
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

LuoTianyi дала вам массив $$$a$$$ из $$$n$$$ целых чисел, нумерация начинается с $$$1$$$.

Определим $$$g(i,j)$$$ следующим образом:

  • $$$g(i,j)$$$ равно наибольшему целому числу $$$x$$$, которое удовлетворяет условию $$$\{a_p:i\le p\le j\}\subseteq\{a_q:x\le q\le j\}$$$, при $$$i \le j$$$;
  • $$$g(i,j)=0$$$ при $$$i>j$$$.

Есть $$$q$$$ запросов. В каждом запросе вам даны четыре целых числа $$$l,r,x,y$$$. Вам нужно посчитать $$$\sum\limits_{i=l}^{r}\sum\limits_{j=x}^{y}g(i,j)$$$.

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$) — элементы массива $$$a$$$.

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

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

Выведите $$$q$$$ строк, где $$$i$$$-я строка содержит одно целое число — ответ на $$$i$$$-й запрос.

Примеры
Входные данные
6 4
1 2 2 1 3 4
1 1 4 5
2 3 3 3
3 6 1 2
6 6 6 6
Выходные данные
6
6
0
6
Входные данные
10 5
10 2 8 10 9 8 2 1 1 8
1 1 10 10
2 2 3 3
6 6 6 6
1 1 4 5
4 8 4 8
Выходные данные
4
2
6
4
80
Примечание

В первом примере:

Для первого запроса ответ равен $$$g(1,4)+g(1,5)=3+3=6$$$.

$$$x=1,2,3$$$ могут удовлетворять условию $$$\{a_p:1\le p\le 4\}\subseteq\{a_q:x\le q\le 4\}$$$, $$$3$$$ является наибольшим числом, поэтому $$$g(1,4)=3$$$.

Для второго запроса ответ равен $$$g(2,3)+g(3,3)=3+3=6$$$.

Для третьего запроса ответ равен $$$0$$$, потому что все $$$i > j$$$ и $$$g(i,j)=0$$$.

Для четвёртого запроса ответ равен $$$g(6,6)=6$$$.

Во втором примере:

Для второго запроса ответ равен $$$g(2,3)=2$$$.

Для четвёртого запроса ответ равен $$$g(1,4)+g(1,5)=2+2=4$$$.