Masala C
Mukofot
Botir aka zavodni muvaffaqiyatli boshqarib, oy oxirida \(n\) ta xodimiga mukofot bermoqchi.
Xodimlar bir qatorda turishadi va chap tarafdan \(1\) dan \(n\) gacha raqamlangan. Har bir xodimning ish samaradorligi \(p_i\) butun son bilan ifodalangan.
Xodimlar bir-birini yaxshi taniydi. Har bir xodim o'zining chap va/yoki o'ng qo'shnilari orasida o'zidan samaradorligi qat'iy yuqori bo'lganlarning sonini biladi. Bu sonni xodimning bosimi deb ataymiz.
Botir aka quyidagi qoidaga amal qilmoqchi: agar ikkita qo'shni xodimdan birining bosimi ikkinchisidan qat'iy katta bo'lsa, u qat'iy ko'proq mukofot olishi shart. Bosimlar teng bo'lsa — hech qanday cheklov yo'q.
Barcha mukofotlar musbat butun son bo'lishi kerak (kamida \(1\) so'm).
Botir aka xarajatni imkon qadar kamaytirmoqchi. Minimal umumiy mukofot summasini toping.
Birinchi qatorda butun son \(t\) — test-caselar soni.
Har bir test-case uchun:
Birinchi qatorda butun son \(n\) — xodimlar soni.
Ikkinchi qatorda \(n\) ta butun son \(p_1, p_2, \ldots, p_n\) — xodimlarning ish samaradorliklari.
\(1 \le t \le 10^4\)
\(1 \le n \le 2 \times 10^5\)
\(1 \le p_i \le 10^9\)
Barcha \(n\) larning yig'indisi \(2 \times 10^5\) dan oshmaydi.
Har bir test-case uchun bitta butun son — minimal umumiy mukofot summasini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 3 1 4 1 5 |
7 |
| 2 |
4 2 2 2 2 |
4 |
| 3 |
5 1 2 3 4 5 |
6 |
1-test: \(p = [3, 1, 4, 1, 5]\)
Bosimlarni hisoblaymiz: \(i=1\) uchun o'ng qo'shni \(1 < 3\), shuning uchun bosim \(= 0\); \(i=2\) uchun chap \(3 > 1\) va o'ng \(4 > 1\), bosim \(= 2\); \(i=3\) uchun chap \(1 < 4\) va o'ng \(1 < 4\), bosim \(= 0\); \(i=4\) uchun chap \(4 > 1\) va o'ng \(5 > 1\), bosim \(= 2\); \(i=5\) uchun chap \(1 < 5\), bosim \(= 0\).
Bosimlar: \([0, 2, 0, 2, 0]\). Qo'shni juftliklar uchun majburiyatlarni hisobga olsak, minimal to'g'ri topshiriq \([1, 2, 1, 2, 1]\) bo'lib, jami \(= 7\).
2-test: Barcha samaradorliklar teng, shuning uchun barcha bosimlar \(0\). Hech qanday cheklov yo'q — hammaga \(1\) beriladi, jami \(= 4\).
3-test: \(p = [1, 2, 3, 4, 5]\) — o'suvchi ketma-ketlik. Bosimlar: \([1, 1, 1, 1, 0]\). Faqat oxirgi juftda bosim farqi bor (\(1\) vs \(0\)), shuning uchun minimal topshiriq \([1, 1, 1, 2, 1]\), jami \(= 6\).
Telegram kanalimizga obuna bo'ling