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