E. Цагдаагийн машин

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

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

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

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

Танай хот нь хязгааргүй 2D хавтгай дээрх Картесианы координатын систем гэж үзье. Танай хотын гэмт хэрэгт өртсөн цорын ганц зам нь $x$ тэнхлэг байв. Одоогоор уг замын дагуу $n$ ширхэг гэмт хэрэгтэй байгаа ба уг зам дээр ямар ч цагдаагийн хэсэг хараахан баригдаагүй байгаа юм. Иймд хотын дарга уг зам дээр шинэ цагдаагийн хэсэг барихыг хүсэж байгаа юм.

Та уг шинэ цагдаагийн хэсгийн дарга болох гэж байгаа учраас хотын дарга таныг үүнийг барих тохиромжтой байрлалыг сонгохыг хүсжээ (ямар нэгэн бүхэл тоон цэг байна). Та уг цагдаагийн хэсэгт зориулан хамгийн оновчтой байрлалыг сонгох ёстой ба ингэснээр гэмт хэрэгтнүүдийг барих ажиллагаанд зарцуулах нийт хугацаа нь хамгийн бага байх ёстой. Гэмт хэрэгтнийг барих таны ажиллагаа зөвхөн уг цагдаагийн хэсгээс эхлэх юм.

Шинэ цагдаагийн хэсэг нь ганцхан цагдаагийн машинтай байна. Та гэмт хэрэгтнүүдийн араас явахдаа уг машинаар явах ба тэдгээрийг уг машинаар зөөн цагдаагийн хэсэгт авчран шоронд хорих юм. Цагдаагийн машин нь нэгэн зэрэг хамгийн ихдээ $m$ ширхэг гэмт хэрэгтэй зөөх боломжтой. Гэмт хэрэгтнүүд нь таны уг ажиллагааг мэдэхгүй байгаа бөгөөд иймд тэд зугтахын оронд байгаа газраа хүлээж байхыг анхаарна уу.

Таны даалгавар бол бүх гэмт хэрэгтнүүдийг барихын тулд таны туулах нийт зам нь боломжит хамгийн бага байх цагдаагийн хэсгийн байрлалыг олох явдал юм. Мөн та нэг эсвэл олон тооны гэмт хэрэгтэн аль хэдийн оршин байгаа байрлал дээр цагдаагийн хэсгийг барьж болохыг анхаарна уу. Ингэсэн тохиолдолд тэдгээр гэмт хэрэгтнүүд нь шууд баривчлагдана гэж үзнэ.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 2 бүхэл тоо $n (1 ≤ n ≤ 10^{6})$ болон $m (1 ≤ m ≤ 10^{6})$ өгөгдөнө. Дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоо өгөгдөнө. Эдгээрийн $i$-дахь бүхэл тоо нь $i$-дахь гэмт хэрэгтний $x$ тэнхлэг дээрх байрлалыг илэрхийлнэ. Эдгээр байрлалуудын абсолют утга нь $10^{9}$-өөс хэтрэхгүй. Хэрэв гэмт хэрэгтэн нь $x$ байрлал дээр байвал тэрээр хавтгайн $(x, 0)$ цэг дээр байрласан гэсэн үг юм.

Гэмт хэрэгтнүүдийн байрлалууд нь үл буурах дарааллаар өгөгдөнө. Хавтгайн ямар нэг цэг дээр нэгээс илүү тооны гэмт хэрэгтэн байж болохыг анхаарна уу.

Анхаар: оролт/гаралтын хэмжээ нь маш том байж болох учраас та өөрийн ашиглаж буй хэл дээрээ удаан оролт/гаралтын арга бүү хэрэглэнэ үү. Жишээлбэл C++ дээр оролт/гаралтын streams (cin, cout)-г бүү хэрэг.

Гаралт

Бүх гэмт хэрэгтнүүдийг барихын тулд таны туулах ёстой боломжит хамгийн бага замын утгыг хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3 6
1 2 3
Гаралт
4
Оролт
5 5
-7 -6 -3 -1 1
Гаралт
16
Оролт
1 369
0
Гаралт
0
Оролт
11 2
-375 -108 1336 1453 1598 1892 2804 3732 4291 4588 4822
Гаралт
18716
Сэтгэгдлүүдийг ачааллаж байна...