A. Дайчин ба Харваач

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

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

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

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

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

Вова ба Леша найзууд. Тэд ихэнхдээ Вовагийнд уулздаг ба Эртний Папири: Свордсинк нэртэй компьютер тоглоомоор биенийхээ эсрэг өрсөлддөг. Вова үргэлж өөрийн тулаанчаар дайчин сонгодог бол Лешак харваачийг сонгодог. Үүний дараа тэд баатруудынхаа эхлэх байрлалыг сонгодог ба тулалдуулж эхэлнэ. Дайчин гардан тулаандаа сайн ба Вова тулаанчдын хоорондох зайг боломжит хамгийн бага байлгахыг оролдоно. Харваач дайсанг аль болох хол байлгахыг илүүд үзэх ба Леша эхлэх зайг аль болох хол байлгах гэж оролдоно.

Энд $n$ ($n$ нь үргэлж тэгш байна) боломжит баатруудын эхлэх байрлал байх ба $Ox$ тэнхлэгийн дагуу тэмдэглэгдсэн байна. Байрлалууд тэдний ялгаатай координатуудаар $x_{1}, x_{2}, ..., x_{n}$ өгөгдсөн ба хоёр баатар ижил байрлалд дуусч болохгүй.

Вова Леша хоёр боломжит байрлалуудыг хасах маягаар ээлжлэх ба Вова эхлэнэ. Залуус нэг ээлжинд үлдсэн байрлалуудаас яг нэг байрлал хасна. Хасагдсан байрлалуудыг Вова Леша хоёулаа ашиглаж чадахгүй. Тэд хоёр боломжит байрлал үлдэх хүртэл хасах үйлдлээ хийсээр байна (иймээс нийт үйлдлийн тоо $n - 2$ байх болно). Үүний дараа Вовагийн баатар бага координаттай байрлалд харин Лешагийн баатар их координаттай байрлалд байрлах ба залуус тулалдаж эхэлнэ.

Вова Леша хоёр тоглолт бүрийн өмнө тоглоомын байрлалуудыг сонгосоор байгаад аль хэдийн ядарчихсан ба таниас (Эртний Папири: Свордсинк тоглоомын хөгжүүлэгч) Вова Леша хоёр хамгийн тохиромжтой байдлаар тоглосон бол дайчин болон харваачийн тулалдаж эхлэх зайг автоматаар тодорхойлдог модулийг бичиж өгөөч гэж асууж байна.

Оролт

Оролтын эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($2 ≤ n ≤ 200 000$, $n$ нь тэгш) байх ба анх идэвхтэй байгаа байрлалуудын тоо. Хоёр дахь мөрөнд ялгаатай $n$ ширхэг бүхэл тоон утга $x_{1}, x_{2}, ..., x_{n}$ ($0 ≤ x_{i} ≤ 10^{9}$) байх ба харгазах байрлалуудын координатуудыг өгч байна.

Гаралт

Вова Леша хоёр хамгийн тохиромжтой байдлаар тоглосон бол тулааны эхэнд дайчин болон харваачийн хоорондох зайг хэвлэ.

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

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

Оролт
6
0 1 3 7 15 31
Гаралт
7
Оролт
2
73 37
Гаралт
36

Тэмдэглэл

Эхний жишээн дээр тоглогчдын хамгийн тохиромжтой байдал нь дараах байдалтай харагдана:

  1. Вова $15$ координаттай байрлалыг хасна;
  2. Леша $3$ координаттай байрлалыг хасна;
  3. Вова $31$ координаттай байрлалыг хасна;
  4. Леша $1$ координаттай байрлалыг хасна.

Эдгээр үйлдлүүдийн дараа зөвхөн $0$ ба $7$ байрлалууд үлдэх ба эдгээрийн хоорондох зай нь $7$-той тэнцүү.

Хоёр дахь жишээн дээр боломжит хоёр байрлал байгаа ба ямар ч байрлал хасахгүй.

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