Деякі складні формули

Дано ціле число $n$ та масив $a_1,a_2,\dots ,a_n$, що складається з $n$ цілих чисел.

Підмасив масиву $a$, що починається з $i$ та закінчується $j$, являє собою відрізок чисел $a_i,a_{i+1},\dots ,a_j$. Назвемо цей підмасив хорошим, якщо

Тобто, якщо найбільший спільний дільник чисел $a_i,a_{i+1},\dots ,a_j$ дорівнює їх середньому арифметичному.

Вам потрібно знайти кількість різних пар цілих чисел $(i,j)$ $(1\le i\le j\le n)$ таких, що підмасив $a_i,a_{i+1},\dots ,a_j$ є хорошим. Також вам необхідно знайти максимальну довжину хорошого підмасиву в $a$.

Вхідні дані

Перший рядок містить одне ціле число $n$ $(1\le n\le 10^5)$ — кількість елементів у масиві $a$.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 10^9)$ — елементи масиву.

Вихідні дані

У єдиному рядку вихідних даних необхідно вивести кількість хороших підмасивів масиву $a$ та довжину найбільшого такого підмасиву.

Приклади

Примітка

У першому прикладі є всього $6$ підмасивів: $(1,1)$, $(1,2)$, $(1,3)$, $(2,2)$, $(2,3)$ та $(3,3)$.

Підмасив $(1,1)$ є хорошим, оскільки $GCD(a_1)=a_1=\frac{a_1}{1}$.

Підмасив $(2,3)$ не є хорошим, оскільки $GCD(a_2,a_3)=GCD(3,2)=1\ne \frac{a_2+a_3}{2}=\frac{3+2}{2}=2.5$.

У цьому масиві рівно 3 хороші підмасиви: $(1,1)$, $(2,2)$, $(3,3)$, і всі з них мають довжину $1$.

Оцінювання

1. ($36$ балів): $n\le 200$;

2. ($64$ бали): $n\le 2000$;

3. ($100$ балів): без додаткових обмежень.