Ділиться на 3#10884
Для масиву цілих чисел [b_1, b_2, ..., b_m] визначимо його вагу як суму попарних добутків його елементів, тобто як суму b_i \cdot b_j для всіх 1 \le i < j \le m.
Дано масив цілих чисел [a_1, a_2, ..., a_n]. Потрібно знайти кількість пар чисел (l, r) таких, що 1 \le l \le r \le n, для яких вага підмасиву [a_l, a_{l+1}, ..., a_r] ділиться на .
Перший рядок містить одне число n~(1 \le n \le 5 \cdot 10^5) — довжину масиву.
Другий рядок містить цілих чисел a_1, a_2, ..., a_n~(0 \le a_i \le 10^9) — елементи масиву.
Виведіть одне ціле число — кількість пар цілих чисел (l, r), де 1 \le l \le r \le n, для яких вага відповідного підмасиву ділиться на .
Приклад 1
Приклад 2
Приклад 3