B1. Цахилгаан бичлэг

хугацааны хязгаарлалт 0.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Орчин үеийн хөл хөдөлгөөнтэй амьдралд ихэнх хүмүүс дэлхий ямар сайхан бэ гэдгийг мартжээ. Эмнэлгийн хэд хэдэн өрөөний үүдэнд үүсэх дарааллуудруу гүйж, олон дараалалд зэрэг зогсдог гэж бодохоор эргэн тойрноо мэдрэх цаг тун хомс байх нь тодорхой.

(Тэмдэглэл: Орос улсад маш урт, зохион байгуулалтгүй дараалалд хэдэн цагаар зогсох нь энгийн үзэгдэл ба Зөвлөлтийн үеийг санагдуулна. Дарааллууд нь шугамыг биш бөөгнөрөлийг санагдуулна. Ийм дараалалд байраа алдахгүйн тулд та дараах аргыг ашиглана: дараалалд ирээд хамгийн сүүлийн хүн хэн бэ гэж асууна хэн нэгэн хариулангуут түүний ард очиж зогсон бөөгнөрөлд нэгдэнэ. Ингээд дараагийн хүн иртэл та дарааллын хамгийн сүүлийн хүн болно. Та дараалал дахь байраа алдалгүй хүссэн үйлчилгээндээ очих хүртлээ таныг ирэхээс өмнө хамгийн сүүлийн хүн байсан хүнээсээ хараагаа салгаж болохгүй.) Танихгүй хүн ирээд дарааллын сүүлийн хүн хэн бэ гэж асуухад маш олон хүнд асуудал үүсдэг гэдэгт би итгэлтэй байна, шинэ хүн хаана зогсохоо тодорхой мэдэхгүй хаа нэгтээ очоод зогсчихдог. Эдгээр зүйлс бол гадаадын алдартай телевизийн шоунуудыг ч үзэж амжхааргүй цагийн хомсдолд орсон орчин үеийн дэлхийн дүрслэл юм. Ийм хүмүүс дараалалд ихэнхдээ асуудал үүсгэдэг, учир нь шинэ ирсэн хүн дараалал дахь сүүлийн хүнийг мэдэхгүй ба энэ үлгэр домгийн дарааллын яг хаана дуусч байгаа юм бол гэж гайхан дарааллыг хийсвэрээр төсөөлөн ард нь зогсоно.

Ухаалаг минж өвдчихөөд байгаа ба эмчтэй уулзсан. Эмч түүнд зүрхний бичлэг хийх хэрэгтэй гэж товч хэлсэн. Маргааш нь Ухаалаг минж эртлэн босоод, алдартай телевизийн цувралыг татаж тавьсан (цувралыг татаж дуустал гурван цаг болно). Минж шүдээ зуугаад эмнэлгийн хамгийн урт дараалал үүсдэг цахилгаан бичлэгний өрөөний үүдэн дахь дараалалруу зориг гарган явсан.

Дараалалд гурван цаг зогссоны дараа Ухаалаг минж тэнд маш эмх замбараагүй мөн олон минж тэдний өмнө хэн зогсож байсныг харахгүй байгааг анзаарсан. Тэр цахилгаан бичлэгний өрөөний үүдэн дахь дараалалд байгаа минж бүр дээр ирж урд нь хэн байх ёстойг асуусан. Хэрвээ минж дараалал дахь зөв байрлалаа мэдэхгүй бол түүний цахилгаан бичлэгний өрөөнд орох ээлж ирж байж болно эсвэл тэр маш удаан хүлээх ёстой ч байж мэднэ.

Таны таамаглаж байгаачлан Ухаалаг минж гэрлүүгээ яарч байгаа ба тэр танд түүнд туслахад шаардлагатай бүх мэдээллийг өгсөн. Түүнд дарааллынх нь дугаар хэд байхыг олж өгч туслана уу.

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n$ $(1 ≤ n ≤ 10^{3})$ ба $x$ $(1 ≤ x ≤ n)$ байх ба харгалзан дараалалд зогсож байгаа минж нарын тоо ба Ухаалаг минжийн дугаар байна. Эмчийн өрөөнд орох гэж буй минж нар 1-с $n$ хүртэл дугаарлагдсан.

Хоёр дахь мөрөнд $n$ бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ $(0 ≤ a_{i} ≤ n)$ байх ба $i$-р минжийн дагаж буй минжийн дугаар байна. Хэрвээ $a_{i} = 0$ байвал $i$-р минж түүний өмнө хэн байх ёстойг мэдэхгүй гэсэн үг. $a_{i}$ утгууд зөв байна. Энэ нь хамаарлуудын хооронд ямар нэг цикл байхгүй гэсэн үг. Дараалалд нэг минжийг хамгийн ихдээ нэг л минж дагана.

30 оноо авах оролтын хязгаарлал нь (дэд бодлого B1):

  • тэг байх $a_{i}$ элементүүдийн тоо $20$-с хэтрэхгүй.

100 оноо авах оролтын хязгаарлал нь (дэд бодлогуул B1+B2):

  • тэг байх $a_{i}$ элементүүдийн тоо дурын байна.

Гаралт

Дараалал дахь Ухаалаг минжийн боломжит байрлалуудын дугааруудыг өсөх дарааллаар нэг, нэг мөрөнд хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
6 1
2 0 4 0 6 0
Гаралт
2
4
6
Оролт
6 2
2 3 0 5 6 0
Гаралт
2
5
Оролт
4 1
0 0 0 0
Гаралт
1
2
3
4
Оролт
6 2
0 0 1 0 4 5
Гаралт
1
3
4
6

Тэмдэглэл

Дөрөвдүгээр жишээний зураг.

Сэтгэгдлүүдийг ачааллаж байна...