PIIMA

Xotira 256 MB Vaqt 1000 ms

14

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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

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

Misollar

#	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

Izoh:

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.

Masala D

Masalalar tuzuvchi kengash