O. Онлайн: сколько среди первых

Дан массив из $n$ чисел. Ответьте на $q$ запросов «сколько среди первых $i$ элементов значений, не превосходящих $x$» — но запросы приходят зашифрованными: настоящие параметры получаются из данных прибавлением предыдущего ответа.

Для запроса номер $j$ (нумерация с единицы) по паре $(i_j, x_j)$ из входа вычисляются

где $\text{prev}$ — ответ на предыдущий запрос (для первого запроса $\text{prev} = 0$).

В первой строке — числа $n$ и $q$ ($1 \le n, q \le 2 \cdot 10^5$). Во второй — $n$ чисел ($|a_i| \le 10^9$). В следующих $q$ строках — пары $i_j$ и $x_j$ ($0 \le i_j \le n$, $|x_j| \le 10^9$).

На каждый запрос выведите количество элементов.