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)\).
Выходные данные
Выведите \(q\) строк, где \(i\)-я строка содержит одно целое число — ответ на \(i\)-й запрос.
Примечание
В первом примере:
Для первого запроса ответ равен \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|