Дано ціле число n та масив a1,a2,…,an, що складається з n цілих чисел.
Підмасив масиву a, що починається з i та закінчується j, являє собою відрізок чисел ai,ai+1,…,aj. Назвемо цей підмасив хорошим, якщо
Тобто, якщо найбільший спільний дільник чисел ai,ai+1,…,aj дорівнює їх середньому арифметичному.
Вам потрібно знайти кількість різних пар цілих чисел (i,j) (1≤i≤j≤n) таких, що підмасив ai,ai+1,…,aj є хорошим. Також вам необхідно знайти максимальну довжину хорошого підмасиву в a.
Перший рядок містить одне ціле число n (1≤n≤105) — кількість елементів у масиві a.
Другий рядок містить n цілих чисел a1,a2,…,an (1≤ai≤109) — елементи масиву.
У єдиному рядку вихідних даних необхідно вивести кількість хороших підмасивів масиву a та довжину найбільшого такого підмасиву.
У першому прикладі є всього 6 підмасивів: (1,1), (1,2), (1,3), (2,2), (2,3) та (3,3).
Підмасив (1,1) є хорошим, оскільки GCD(a1)=a1=1a1.
Підмасив (2,3) не є хорошим, оскільки GCD(a2,a3)=GCD(3,2)=1=2a2+a3=23+2=2.5.
У цьому масиві рівно 3 хороші підмасиви: (1,1), (2,2), (3,3), і всі з них мають довжину 1.
(36 балів): n≤200;
(64 бали): n≤2000;
(100 балів): без додаткових обмежень.