C. Жуулчны тэмдэглэл

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

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

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

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

Жуулчин ууланд явган аялал хийжээ. Явган аялал $n$ хоногийн турш үргэлжилсэн бөгөөд жуулчин өдөр бүр далайн түвшнээс дээш хэдэн метр өндөрт яваа тайлбараа тэмдэглэдэг байна. $i$-р өдөр $h_{i}$ өндөрт байна. Жуулчин өөрийн явган аялалд аль болох дардан замыг сонгоно, энэ нь дараалсан хоёр өдрийн өндрийн өөрчлөлт хамгийн ихдээ $1$ байна гэсэн үг. Өөрөөр хэлбэл $1$-ээс $n - 1$ хүртэлх бүх $i$-н хувьд $|h_{i} - h_{i + 1}| ≤ 1$ тэнцэтгэл бишийг хангана.

Замын төгсгөлд жуулчин уулын голыг доош гатлан гарахдаа өөрийн тэмдэглэлийн зарим тайлбарыг усанд норгочихжээ. Үүгээр ч барахгүй тайлбарын зарим тоонуудын хэлбэр дүрс нь алдагдаад ойлгогдохгүй болсон байжээ. Одоо жуулчин аялалын туршид хамгийн ихдээ ямар өндөрт байсан бол гэж боджээ. Явган аялалын туршид явсан боломжит хамгийн их өндрийн утгыг сэргээхэд түүнд туслах, эсвэл $|h_{i} - h_{i + 1}| ≤ 1$ тэнцэтгэл бишийг хангах өндрүүдийн утга байхгүй буюу тайлбарт зөрчил байгаа эсэхийг тодорхойлно уу.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан $n$, $m$ ($1 ≤ n ≤ 10^{8}$, $1 ≤ m ≤ 10^{5}$) бүхэл тоонууд байх ба эдгээр нь явган аялал хийсэн өдрүүдийн тоо болон ус ороогүй үлдсэн тайлбарын тоог илэрхийлнэ. Тайлбарууд он цагийн дарааллаар өгөгдөнө. Өөрөөр хэлбэл $1$-ээс $m - 1$ хүртэлх бүх $i$-н хувьд $d_{i} < d_{i + 1}$ тэнцэтгэл бишийг хангана.

Гаралт

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

Хэрвээ өндрүүдийн ямар ч олонлог тайлбарт нийцэхгүй бол "IMPOSSIBLE" гэж хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
8 2
2 0
7 0
Гаралт
2
Оролт
8 3
2 0
7 0
8 3
Гаралт
IMPOSSIBLE

Тэмдэглэл

Эхний жишээнд боломжит хамгийн өндөр нь $2$ байх зөв дарааллын жишээ: $(0, 0, 1, 2, 1, 1, 0, 1)$.

Хоёр дахь жишээнд $h_{7}$ болон $h_{8}$ өндрүүд дээр тэнцэтгэл биш биелэхгүй байна. Тиймээс энэ мэдээлэл зөрчилтэй байна.

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