Masala #MOKUEJURCZ

Yaqin Sharq mintaqasida, uzoq o‘tmishda mavjud bo‘lgan ilmiy bilimlar markazi – Al-Muazzam kutubxonasi haqida afsona mavjud. Bu kutubxona o‘z vaqtida minglab noyob qo‘lyozmalar, ilmiy risolalar, falakiyot jadvali va tilshunoslikka oid asarlarni o‘zida saqlagan. Ammo yillar o‘tishi bilan bu kutubxona vayron bo‘lgan va faqat afsonalarda saqlanib qolgan. Tarixiy manbalarda aytilishicha, bu kutubxonada mavjud bo‘lgan har bir asar o‘ziga xos raqamli kodga ega bo‘lgan, va u kodlar orqali asarlar joylashuvi aniq belgilab qo‘yilgan.

Aynan shu raqamli kodlar asosida olimlar kutubxonani tiklash ustida ishlamoqdalar. Siz tarixchi-kriptolog sifatida bu kodlarning ma'nosini tushunish bilan shug‘ullanasiz.

Sizga uzunligi n ga teng bo‘lgan massiv – A[1..n] beriladi. Har bir A[i] musbat butun son bo‘lib, bu sonlar qadimiy kitoblarning raqamli identifikatorlari sifatida qabul qilinadi.

Afsonaga ko‘ra, har bir kitob "Afsona bo‘lishi uchun" quyidagi shartga javob beradigan segmentda bo‘lishi kerak:

• Har qanday l va r (1 ≤ l ≤ r ≤ n) uchun segment A[l..r] afsonaviy segment deb ataladi, agar bu segmentdagi har bir element kamida bir marta bu segmentdagi barcha elementlarning o‘rtacha qiymatiga teng bo‘lsa.

Bu degani, A[l..r] dagi har bir sonlar orasida shunday bir A[k] mavjud bo‘lishi kerakki, uning qiymati ushbu segmentdagi sonlarning o‘rtachasiga teng (aniq son emas, butun qiymatga ega bo‘lishi shart).

Kiritish Formati:

Birinchi qatorda butun son n (1 ≤ n ≤ 10**4) — massiv elementlari soni.

Ikkinchi qatorda n ta butun son A[1], A[2], ..., A[n] (1 ≤ A[i] ≤ 10**7) — qadimiy kitoblar kodlari.

Chiqish Formati:

Yagona satrda — afsonaviy segmentlar sonini chiqaring.