Bəzi mürəkkəb düsturlar

Tam ədəd $n$ və $n$ sayda tam ədədlərdən ibarət $a_1,a_2,\dots ,a_n$ massivi verilir.

$a$ massifinin başlanğıcı $i$ və sonu $j$ olan altmassivi, $a_i,a_{i+1},\dots ,a_j$ ədədlər ardıcıllığıdır. Bu altmassivi o zaman yaxşı adlandırırıq ki,

olur. Yəni, ədədlərin $a_i,a_{i+1},\dots ,a_j$ ən böyük ortaq böləni onların ədədi ortasına bərabərdir.

Sizdən $a_i,a_{i+1},\dots ,a_j$ altmassivi yaxşı olan fərqli tam ədədlər cütlüklərinin sayını $(i,j)$ $(1\le i\le j\le n)$ və $a$-nın yaxşı altmassivinin maksimum uzunluğunu tapmaq tələb olunur.

Giriş verilənləri

Birinci sətirdə, $n$ $(1\le n\le 10^5)$ — $a$ massivindəki elementlərin sayı verilir.

İkinci sətirdə, $n$ tam ədəd $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 10^9)$ — massivin elementləri verilir.

Çıxış verilənləri

Yeganə sətirdə, $a$ massivinin yaxşı altmassivlərinin sayını və ən uzun altmassivin uzunluğunu çap etmək lazımdır.

Nümunələr

Qeyd

İlk nümunədə, ümumilikdə $6$ altmassiv var: $(1,1)$, $(1,2)$, $(1,3)$, $(2,2)$, $(2,3)$ və $(3,3)$

$(1,1)$ altmassivi yaxşı olduğu üçün ki, $GCD(a_1)=a_1=\frac{a_1}{1}$.

$(2,3)$ altmassivi yaxşı deyil, çünki $GCD(a_2,a_3)=GCD(3,2)=1\ne \frac{a_2+a_3}{2}=\frac{3+2}{2}=2.5$.

3 yaxşı alt array var: $(1,1)$, $(2,2)$, $(3,3)$ və bütün bu alt arraylar uzunluğa sahibdirlər $1$.

Qiymətləndirmə

1. ($36$ xal): $n\le 200$;

2. ($64$ xal): $n\le 2000$;

3. ($100$ xal): əlavə məhdudiyyətlər yoxdur.