Бурёнка пришла смотреть самое интересное спортивное событие года — турнир по борьбе, организованный её другом Тоней.
В турнире участвует \(n\) спортсменов, им были выданы номера от \(1\) до \(n\). Для спортсмена с \(i\)-м номером Бурёнка определила его силу — целое число \(a_i\), где \(1 \leq a_i \leq n\). Все силы различны, то есть массив сил \(a\) является перестановкой длины \(n\). Известно, что если \(a_i > a_j\), то \(i\)-й участник всегда побеждает \(j\)-го
Турнир проходит так: сначала все \(n\) спортсменов встают в очередь по возрастанию своих номеров, а затем происходит бесконечно много туров. В каждом туре происходит ровно один поединок между первыми двумя спортсменами из очереди. Победитель возвращается в начало очереди, а проигравший встаёт в её конец.
Бурёнка решила задать Тоне \(q\) вопросов. В каждом вопросе Бурёнка спрашивает, сколько побед \(i\)-й спортсмен одержит за первые \(k\) туров соревнования для некоторых \(i\) и \(k\). Тоня не очень хорош в аналитике, поэтому просит вас помочь ему с ответом на все вопросы.
Выходные данные
На каждый вопрос Бурёнки выведите единственную строку, содержащую одно целое число — ответ на вопрос.
Примечание
В первом наборе входных данных первый по номеру спортсмен имеет силу \(3\), в первом туре он победит спортсмена с номером \(2\) и силой \(1\), а во втором — спортсмена с номером \(3\) и силой \(2\).
Во втором наборе входных данных перечислим силы спортсменов, дерущихся в первых \(5\) боях: \(1\) и \(3\), \(3\) и \(4\), \(4\) и \(2\), \(4\) и \(1\), \(4\) и \(3\). Участник с номером \(4\) в первых \(5\) турах одержал \(0\) побед (его сила равна \(2\)). Участник с номером \(3\) имеет силу \(4\) и в первых двух боях одержал \(1\) победу, проведя \(1\) бой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 1
3 1 2
1 2
4 2
1 3 4 2
4 5
3 2
5 2
1 2 3 5 4
5 1000000000
4 6
|
2
0
1
0
4
|