Tam ədəd n və n sayda tam ədədlərdən ibarət a1,a2,…,an massivi verilir.
a massifinin başlanğıcı i və sonu j olan altmassivi, ai,ai+1,…,aj ədədlər ardıcıllığıdır. Bu altmassivi o zaman yaxşı adlandırırıq ki,
olur. Yəni, ədədlərin ai,ai+1,…,aj ən böyük ortaq böləni onların ədədi ortasına bərabərdir.
Sizdən ai,ai+1,…,aj altmassivi yaxşı olan fərqli tam ədədlər cütlüklərinin sayını (i,j) (1≤i≤j≤n) və a-nın yaxşı altmassivinin maksimum uzunluğunu tapmaq tələb olunur.
Birinci sətirdə, n (1≤n≤105) — a massivindəki elementlərin sayı verilir.
İkinci sətirdə, n tam ədəd a1,a2,…,an (1≤ai≤109) — massivin elementləri verilir.
Yeganə sətirdə, a massivinin yaxşı altmassivlərinin sayını və ən uzun altmassivin uzunluğunu çap etmək lazımdır.
İ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(a1)=a1=1a1.
(2,3) altmassivi yaxşı deyil, çünki GCD(a2,a3)=GCD(3,2)=1=2a2+a3=23+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.
(36 xal): n≤200;
(64 xal): n≤2000;
(100 xal): əlavə məhdudiyyətlər yoxdur.