Masala #IHKE52L1UH
Masalalar tuzuvchi kengash
Informatika fanidan olimpiadalarga masala tuzuvchi kengashda jami \(N\) nafar a’zo bor. Yaqinda bo‘lib o‘tadigan musobaqa uchun kengashning \(i\)-a’zosi \(a_i\) ta masala taklif qildi. Boshqa nufuzli kengashdagi kabi bu kengashning ham o‘z boshlig‘i bor. Kengashning boshlig‘i taklif qilingan masalalarni rad etish huquqiga ega. Komitet boshlig‘ining fikricha musobaqa yaxshi o‘tishi uchun musobaqada hech kim undan ko‘proq masala tuzmasligi lozim. Ya’ni kengashning \(j\)-a’zosi boshliq bo‘lsa, barcha \(i(1 \leq i \leq N)\) uchun \(a_i \leq a_j\) sharti qanoatlantirilishi lozim.
Sizning vazifangiz har bir \(i(1 \leq i \leq N)\) uchun kengashning \(i\)-a’zosi boshliq bo‘ladigan bo‘lsa, musobaqa yaxshi o‘tishi uchun rad etilishi kerak bo‘lgan minimal masalalar sonini chiqaring. E’tibor bering, musobaqa uchun masalalar qolmasligi ham mumkin.
Birinchi qatorda bitta butun son - \(N (1 \leq N \leq 2*10^5)\) kiritiladi.
Ikkinchi qatorda probel bilan ajratilgan \(N\) ta son - \(a_i(1 \leq a_i \leq 10^9)\) qiymatlari kiritiladi.
\(N\) ta butun son ekranga chiqaring. \(i\)-son \(i\)-kengash a’zosi boshliq bo‘lsa, musobaqa yaxshi o‘tishi uchun rad etish kerak bo‘lgan minimal masalalar sonini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 2 3 1 |
1 0 3 |
| 2 |
6 1 1 0 7 9 12 |
25 25 30 7 3 0 |
1-testda:
1-a’zo kengash boshlig‘i bo‘lsa u faqatgina 2-a’zo taklif qilgan 1 ta masalani rad etsa maqsadga erishadi. Bunda taklif qilingan masalalar \([2, 2, 1]\) bo‘ladi.
2-a’zo kengash boshlig‘i bo‘lsa, hech qaysi masalalar rad etilmasa ham musobaqa yaxshi o‘tadi. Bunda taklif qilingan masalalar \([2, 3, 1]\) bo‘ladi.
3-a’zo kengash boshlig‘i bo‘lsa, 3 ta masala rad etilishi kerak bo‘ladi. Bunda taklif qilingan masalalar \([1, 1, 1]\) ko‘rinishida bo‘lishi kerak.
Telegram kanalimizga obuna bo'ling