Masala M
Sehrli Kartalar
Dilnoza \(n\) ta kartani ketma-ket qatorga yoydi. Har bir kartaning ustida musbat butun son yozilgan.
Dilnoza \(i\)-kartani "oltin" deb ataydi, agar quyidagi shartlardan biri bajarilsa:
- \(i = 1\) bo'lsa (ya'ni karta birinchi bo'lsa), yoki
- \(a_i > a_1 + a_2 + \ldots + a_{i-1}\) bo'lsa (ya'ni kartadagi son, undan oldingi barcha kartalardagi sonlar yig'indisidan qat'iy katta bo'lsa).
Dilnoza nechta oltin karta borligini bilmoqchi. Unga yordam bering!
Kiruvchi ma'lumotlar:
Birinchi qatorda \(n\) — kartalar soni \((1 \le n \le 2 \cdot 10^5)\) beriladi.
Ikkinchi qatorda \(n\) ta musbat butun son \(a_1, a_2, \ldots, a_n\) beriladi \((1 \le a_i \le 10^9)\).
Chiquvchi ma'lumotlar:
Bitta butun son — oltin kartalar sonini chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 3 5 2 11 4 |
3 |
| 2 |
4 1 2 4 8 |
4 |
Izoh:
1-misol: \(n = 5\), kartalar: \([3,\ 5,\ 2,\ 11,\ 4]\).
- \(1\)-karta: \(3\) — birinchi karta, shuning uchun oltin ✓
- \(2\)-karta: \(5\) — oldingi yig'indi \(= 3\), \(5 > 3\) — oltin ✓
- \(3\)-karta: \(2\) — oldingi yig'indi \(= 3+5 = 8\), \(2 > 8\)? — yo'q ✗
- \(4\)-karta: \(11\) — oldingi yig'indi \(= 3+5+2 = 10\), \(11 > 10\) — oltin ✓
- \(5\)-karta: \(4\) — oldingi yig'indi \(= 3+5+2+11 = 21\), \(4 > 21\)? — yo'q ✗
Jami oltin kartalar: \(3\).
Telegram kanalimizga obuna bo'ling