Masala #1034

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 50 %
14

  

Asadbekning gullari

Asadbek gullarni parvarishlashni yoqtiradi. U “Ci plus plusium” gullaridan o‘zining qator joylashgan \(n\) ta tuvagining barchasiga ekdi. Birinchi kuni barcha gullarning bo‘yi 0 deb hisoblasa bo‘ladi. Shu kundan boshlab har kuni Asadbek:

  • shunday \([l, r]\) oraliqni tanlaydiki, shu oraliqdagi barcha tuvaklardagi gullarning bo‘yi  bir xil bo‘lsin;
  • \([l+1,r-1]\) oraliqdagi barcha tuvaklarga suv quyadi. Keyingi kungacha shu oraliqdagi tuvaklarda joylashgan gullar 1 birlikka ga o‘sadi.

Misol, \(n=6\) uchun mos ravishda 1-2-3-kunlardagi gullarning bo‘yini quyidagicha tasvirlash mumkin:

 

1-kuni \([1,6]\) oraliq tanlangan va \([2,5]\) oraliqdagi tuvaklarga suv quyilgan.

2-kuni \([3,5]\) oraliq tanlangan va \([4,4]\) oraliqdagi tuvaklarga suv quyilgan.

0 yoki bir necha kundan so‘ng, Asadbek o‘zining gullari bilan maqtanmoqchi bo‘lib, har bir gulining bo‘yini \(A\) massiviga yozib, uni sizga berdi (\(A_i=i\)-tuvakdagi gulning bo‘yi). Ammo ba’zi gullarining bo‘ylarini eslay olmagani uchun, ularning bo‘ylarini o‘rniga -1  sonini yozdi.

Sizning vazifangiz Asadbek bergan ma’lumotlarga ko‘ra, bugungi kunda uning gullari necha xil ko‘rinishda bo‘lishi mumkinligini sanashdir. Agarda Asadbek sizni aldagan bo‘lsa, 0 chiqaring.

Natija katta bo‘lishi mumkinligi sababli, natijani \(10^9+7\) ga bo‘lingandagi qoldig‘ini chiqaring.


Kiruvchi ma'lumotlar:

Kirish oqimining birinchi qatorida bitta butun son - \(n(1 \le n \le 10^4)\) kiritiladi.

Keyingi qatorda \(n\) ta butun son - Asadbek sizga bergan \(A\) massiv elementlari kiritiladi. Massiv elementlari yoki -1 yoki \(10^4\) dan oshmaydigan butun manfiy bo‘lmagan sonlardir.


Chiquvchi ma'lumotlar:

Hozir Asadbekning gullari necha xil ko‘rinishda bo‘lishi mumkin ekanligini \(10^9+7\) ga bo‘lgandagi qoldig‘ini chiqaring. U aldagan bo‘lsa 0 chiqaring.


Misollar
# input.txt output.txt
1
4
-1 -1 3 -1
0
2
6
-1 -1 2 -1 -1 -1
3
Izoh:

Birinchi testda:

Hech qanday usulda \(n=4\) uchun bo‘yi 3 bo‘lgan gul o‘stirib bo‘lmaydi. Demak Asadbek aldagan.

 

Ikkinchi testda:

Asadbekning gullari quyidagi 3 xil ko‘rinishda bo‘lishi mumkin:

\([0,1,2,2,1,0]\);

\([0,1,2,1,1,0]\);

\([0,1,2,1,0,0]\).

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin