F. Следующий и предыдущий
ограничение по времени на тест
15 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$p_1, \ldots, p_n$$$ — перестановка массива $$$[1, \ldots, n]$$$.

Пусть $$$q$$$-последовательность $$$p$$$ — это перестановка $$$[1, q]$$$, элементы которой расположены в том же относительном порядке, что и в $$$p_1, \ldots, p_n$$$. То есть мы извлекаем из $$$p$$$ в исходном порядке все элементы, которые не превосходят $$$q$$$, и они составляют $$$q$$$-последовательность $$$p$$$.

Для заданного массива $$$a$$$ пусть $$$pre(i)$$$ — наибольшее значение, удовлетворяющее $$$pre(i) < i$$$ и $$$a_{pre(i)} > a_i$$$. Если такого значения не существует, пусть $$$pre(i) = -10^{100}$$$. Пусть $$$nxt(i)$$$ — наименьшее значение, удовлетворяющее $$$nxt(i) > i$$$ и $$$a_{nxt(i)} > a_i$$$. Если оно не существует, пусть $$$nxt(i) = 10^{100}$$$.

Для каждого $$$q$$$ такого, что $$$1 \leq q \leq n$$$, пусть $$$a_1, \ldots, a_q$$$ — $$$q$$$-последовательность $$$p$$$. Для каждого $$$i$$$, такого, что $$$1 \leq i \leq q$$$, $$$pre(i)$$$ и $$$nxt(i)$$$ будут вычислены в соответствии с условиями выше. Затем вам будут даны некоторые целые значения $$$x$$$, и для каждого из них вы должны вычислить $$$\sum\limits_{i=1}^q \min(nxt(i) - pre(i), x)$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке находится одно целое число $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^5$$$) — длина перестановки.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — начальную перестановку.

Затем, для каждого $$$q$$$ такого, что $$$1 \leq q \leq n$$$, в порядке возрастания, вам будет дано целое число $$$k$$$ ($$$0 \leq k \leq 10^5$$$), представляющее собой количество запросов для $$$q$$$-последовательности. Затем в строке следуют $$$k$$$ чисел: каждое из них является значением $$$x$$$ для одного запроса ($$$1 \leq x \leq q$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3\cdot 10^5$$$, а сумма $$$k$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных, для каждого запроса выведите одну строку с целым числом — ответом на запрос.

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

$$$1$$$-последовательность — это $$$[1]$$$, причем $$$pre=[-10^{100}]$$$, $$$nxt=[10^{100}]$$$. $$$ans(1)=\min(10^{100}-(-10^{100}),1)=1$$$.

$$$5$$$-последовательностью является $$$[1,4,3,2,5]$$$, причем $$$pre=[-10^{100},-10^{100},2,3,-10^{100}]$$$, $$$nxt=[2,5,5,5,10^{100}]$$$. $$$ans(1)=5,ans(2)=10,ans(3)=14$$$.