E. Диваажингийн Аялал

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

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

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

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

PMP-д бурхан дахин амилах боломжийг хайрлав. Гэхдээ тэр дахин амилахаасаа өмнө $n$ ширхэг агуу хүмүүсийн сүнстэй уулзан тэдний амьдралын туршлагаас хуваалцах ёстой.

Тэдгээр агуу хүмүүс шулуун шугаман дээр зогсож байгаа ба зүүнээсээ баруун тийш 1-ээс $n$ хүртэл дугаартай. $i$-р хүний координат нь $x_i(x_iнэг удаа л уулзана. Энэхүү уулзах аялалын эхэнд PMP $s$-р хүний байрлал дээр байгаа тул тэр хүнтэйгээ уулзчихсан гэж үзнэ.

PMP байрлалаа өөрчлөе гэвэл нэг сахиусан тэнгэрт нэг тасалбараа хураалгахад уг сахиусан тэнгэр түүнийг зорьсон газарт нь нисгэн аваачиж буулгах ба нисэж явах зуураа хүнтэй уулзах боломжгүй. $i$-р хүнээс $j$-р хүнрүү очиход $|x_i-x_j|$ хугацаа шаардагддаг. PMP бүх хүмүүстэй уулзаж дуусангуутаа амилах болно.

Сахиусан тэнгэрүүд нь хоёр төрөл байдаг бөгөөд нэг төрлийнх нь зөвхөн баруун тийш явдаг ба зөвхөн баруун тийш явах тасалбар авдаг, нөгөө төрлийн сахиусан тэнгэрүүд зөвхөн зүүн тийш л явдаг ба зөвхөн зүүн тийш явах тасалбар авдаг. Аль аль төрлийн сахиусан тэнгэрүүд хязгааргүй олон, хангалттай бий. Харин PMP-д $l$ ширхэг зүүн тийш шилжих тасалбар, $n-l-1$ ширхэг баруун тийш явах тасарбар байгаа.

PMP аль болох хурдан амилахыг хүсэж буй тул түүнд хамгийн хурдан амилахад шаардлагатай хугацаа болон ямар дарааллаар хүмүүстэй уулзах хэрэгтэй зэргийг мэдээлнэ үү.

Оролт

Эхний мөрөнд уулзах ёстой хүмүүсийн тоо, зүүн тийш шилжих тасалбаруудын тоо, мөн PMP-н анхны байрлал болох $n, l, s(2<=n<=10^5, 0<=l

Дараагийн мөрөнд $n$ ширхэг хоорондоо хоосон зайгаар тусгаарлагдсан бүхэл тоонууд өгөгдөнө. Энэ мөрний $i(0=x_1

Гаралт

Хэрэв PMP бүх хүмүүстэй уулзаж чадахгүй бол $-1$-ийг, уулзаж чадах бол эхний мөрөнд амилахад шаардлагатай хамгийн бага хугацааг мөн дараагийн мөрөнд нь хүмүүсийг ямар дарааллаар очихыг илэрхийлсэн n-1 ширхэг тоо хэвлэнэ.Хэрэв бодлого олон шийдтэй бол зөвхөн аль нэгий нь хэвлэхэд хангалттай.

Орчуулсан: devman

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

Оролт
5 2 2
0 10 11 21 22
Гаралт
33
1 3 5 4
Оролт
4 3 1
0 1 2 3
Гаралт
-1
Оролт
7 3 2
0 100 200 201 301 303 305
Гаралт
409
1 3 4 7 6 5

Тэмдэглэл

Биднийг жилийн өмнө орхин явсан бүх цагийн үеийн агуу оролцогчийг дурсан санаж байна. Renat Mullakhanov маань диваажинд байгаа байх даа.

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