Muallif: __thecrash__

D. Stikerlar albomi

Vaqt limiti: 1000 ms Xotira limiti: 256 mb

Jasur futbolchilar stikerlarini yig'adi. Albomda \(n + 1\) ta joy bor, ular \(1\) dan \(n + 1\) gacha raqamlangan, har bir raqamli stiker o'z joyiga yopishtiriladi. Albomning to'liq boshlanishi deb albomning \(1\)-joyidan boshlab ketma-ket, orada bo'sh joy qoldirmay to'ldirilgan joylar soniga aytiladi. Masalan, albomda \(1\), \(2\), \(3\) va \(5\) raqamli stikerlar bo'lsa, to'liq boshlanish \(3\) ga teng, chunki \(4\)-joy bo'sh. Agar \(1\)-stiker bo'lmasa, to'liq boshlanish \(0\) ga teng.

Jasur \(n\) kun davomida har kuni bitta stiker oladi. \(i\)-kuni olingan stiker \(a_i\) bilan berilgan. Agar \(a_i \ge 1\) bo'lsa, Jasur \(a_i\) raqamli stikerni oldi. Agar \(a_i = 0\) bo'lsa, u yopiq paket oldi va paketdan \(1\) dan \(n + 1\) gacha bo'lgan istalgan raqamli stiker chiqishi mumkin.

Har bir \(i\) (\(1 \le i \le n\)) uchun quyidagini hisoblang. Birinchi \(i\) kunda olingan barcha yopiq paketlar ichidagi stikerlarning mumkin bo'lgan barcha variantlarini ko'rib chiqamiz. Har bir variant uchun albomning to'liq boshlanishini topamiz va bu sonlarning yig'indisini hisoblaymiz. Ikki variant kamida bitta paketdagi stiker raqami bilan farq qilsa, ular har xil hisoblanadi.


Kiruvchi ma'lumotlar

Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 2 \cdot 10^5\)).

Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le n + 1\)).

Yopiq paketlar soni, ya'ni \(a_i = 0\) bo'lgan kunlar soni \(300\) dan oshmaydi.


Chiquvchi ma'lumotlar

Har bir \(i\) uchun \(1\) dan \(n\) gacha tartib bilan birinchi \(i\) kun uchun hisoblangan yig'indini \(998\,244\,353\) ga bo'lgandagi qoldig'ini chiqaring.

Misollar

# Input.txt Output.txt
1
5
0 2 0 4 0
1 2 24 26 248
2
7
4 6 0 0 0 0 2
0 0 1 17 223 2645 4906
3
10
4 9 6 2 1 1 8 3 3 9
0 0 0 0 2 2 2 4 4 4

Izoh

Birinchi misolda \(i = 3\) ni ko'rib chiqamiz. Birinchi uch kunda ikkita yopiq paket va \(2\)-stiker olingan. Har bir paketdan \(6\) xil stiker chiqishi mumkin, demak jami \(36\) ta variant bor. \(1\)-stiker chiqmagan \(25\) ta variantda to'liq boshlanish \(0\) ga teng. Qolgan \(11\) ta variantdan ikkitasida paketlardan \(1\) va \(3\)-stikerlar chiqadi, u yerda to'liq boshlanish \(3\) ga teng. Qolgan \(9\) tasida esa \(2\) ga teng. Yig'indi \(2 \cdot 3 + 9 \cdot 2 = 24\).

\(i = 4\) bo'lganda \(4\)-stiker qo'shiladi. To'liq boshlanishi \(3\) bo'lgan ikki variantda u \(4\) ga oshadi, shuning uchun javob \(24 + 2 = 26\).

Yechim yuborish uchun tizimga kiring yoki ro'yxatdan o'ting.

Navbatdagi musobaqa

Biriktirilgan musobaqa

SamCoding Round 11 (Div. 1)

Natijalar