A. Unutilgan Afsona

Xotira: 300 MB, Vaqt: 2000 ms

Masala

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).

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Chiqish Formati:

Yagona satrda — afsonaviy segmentlar sonini chiqaring.

Izoh:

Afsonaviy segmentlar:

[1,2,3] → o‘rtacha 2 → mavjud
[2,3,4] → o‘rtacha 3 → mavjud
[3,4,5] → o‘rtacha 4 → mavjud
[1,2,3,4,5] → o‘rtacha 3 → mavjud

bu masala 2100 rating codeforces

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1 2 3 4 5	4

B. Qog‘ozni kesish

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga uzunligi n bo‘lgan qog‘oz berilgan. Qog‘ozning har bir qismi bo‘sh yoki kesilgan bo‘lishi mumkin.

Qog‘ozni kesish o‘yinida siz va raqib har bir o‘z navbatida qog‘ozning har bir bo‘sh qismidan birini kesishingiz mumkin. Har bir kishi faqat bo‘sh joydan kesish huquqiga ega. Agar bir kishi o‘z navbatida kesish imkoniyatiga ega bo‘lmasa, u mag‘lub bo‘ladi.

Vazifa: Agar siz birinchi bo‘lib harakat qilsangiz, g‘alaba qozonishingiz mumkinmi? Agar mumkin bo‘lsa, YES deb chiqaring, aks holda NO.

Kiruvchi ma'lumotlar:

Birinchi qatorda bir butun son n beriladi (1 ≤ n ≤ 1000) — qog‘ozning uzunligi.

Ikkinchi qatorda uzunligi n bo‘lgan satr beriladi, unda . bo‘sh joyni, # esa kesilgan joyni ifodalaydi.

Chiquvchi ma'lumotlar:

Agar siz birinchi bo‘lib g‘alaba qozonishingiz mumkin bo‘lsa, YES chiqaring.
Agar g‘alaba qozonish imkoni bo‘lmasa, NO chiqaring.

Izoh:

Birinchi o‘yinchi har doim bo‘sh joyni tanlashi mumkin, masalan, 1-chi yoki 3-chi joyni kesish orqali o‘yinni boshlash mumkin.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 .#.#.	YES