9 аксиом Вселенной

В мире, где возник конфликт между вами и Злом Чмяааксом, существуют 9 аксиом, которые могут объяснить всё (буквально всё). Тот факт, что их ровно девять, был доказан давно и изучается в школах, но не все аксиомы известны, и не все могут их понять. Если бы кто-то смог раскрыть их все, это открыло бы путь к контролю над вселенной (в самом буквальном смысле). Давным-давно Чмяаакс...

Давайте посмотрим, что там изучают в школах. Вот пример тестового вопроса из 5-го класса, можете ли вы его решить?

Назовем массив $b$ хорошим, если не существует его подотрезка, сумма элементов которого равна 0. Формально: ${\sum }_{i=l}^r{b}_i\ne 0(1\le l\le r\le |b|)$.

Дан массив $a$ длины $n$ и $q$ запросов к нему. Каждый запрос описывается числами $l,r$. Необходимо решить следующую задачу для каждого запроса:

Если рассмотреть подмассив массива $a$ с $l$ по $r$, каково минимальное количество элементов, которые необходимо изменить, чтобы этот подмассив стал хорошим?

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

Первая строка содержит два целых числа $n(1\le n\le 5\cdot 10^5)$ и $q(1\le q\le 5\cdot 10^5)$ — длину массива $a$ и количество запросов.

Вторая строка содержит $n$ целых чисел $a_i(-10^9\le a_i\le 10^9)$ — элементы массива $a$.

Следующие $q$ строк содержат пару целых чисел $l_i,r_i(1\le l\le r\le n)$ — параметры $i$-го запроса.

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

Выведите $q$ целых числа – ответ на каждый запрос.

Примеры

Примечание

В первом запросе первого примера нам нужно решить задачу по всему массиву $a$: $[1,1,0,-1,2,-3]$. Существует подотрезок $[3,3]$, сумма которого равна нулю, поэтому нам нужно сделать как минимум одно изменение в массиве, чтобы сделать его хорошим. Если мы сделаем $a_3=47$, то массив станет хорошим.

В третьем запросе второго примера нам нужно решить задачу по подмассиву $[4,-4,0]$. Мы можем сделать два изменения, чтобы получить $[4,47,47]$, что является хорошим массивом. Можно показать, что это минимальное количество операций, чтобы сделать подмассив хорошим.

Оценивание

1. ($6$ баллов): $n,q\le 15$;

2. ($21$ балл): $n,q\le 5000$;

3. ($24$ балла): Если $[l,r]$ является сегментом с суммой $0$, то $[1,r]$ также является сегментом с суммой $0$;

4. ($24$ балла): Ни два сегмента с суммой $0$ не пересекаются, более формально, если $[l_1,r_1]$ и $[l_2,r_2]$ это два разных сегмента с суммой $0$, то $r_2<l_1$ или $r_1<l_2$;

5. ($31$ балл): $n,q\le 2\cdot 10^5$;

6. ($19$ баллов): без дополнительных ограничений;