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$ балів): без додаткових обмежень;