Какие-то сложные формулы

Дано целое число $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$ баллов): без дополнительных ограничений.