F. Симба тойрог дээр

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

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

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

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

Танд $n$ элементтэй тойрог массив өгөгдсөн. Элементүүд аль нэг элементээсээ эхлэн цагийн зүүний дагуу $1$-с $n$ хүртэл дугаарлагдсан. $i$-р нүд $a_{i}$ утгыг агуулна. Робот Симба $s$ нүдэнд байгаа.

Цагийн мөч бүрт робот $n$ нүднүүдийн аль нэгэнд нь байна (эхлээд тэр $s$ нүдэнд байна). Нэг ээлжинд робот тухайн нүдэнд буй тоог бичиж авах эсвэл цагийн зүүний дагуу эсвэл цагийн зүүний эсрэг чиглэлтэй хөрш нүдэнд шилжиж чадна. Нүднээс тоог бичиж авахад Симба цаг зарцуулахгүй боловч хөрш нүдрүү шилжихэд Симба нэгж хугацаа зарцуулна.

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

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $s$ ($1 ≤ s ≤ n ≤ 2000$) байх ба тойрог массивийн нүдний тоо ба Симбагийн эхлэх байрлал.

Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утгууд $a_{i}$ ($ - 10^{9} ≤ a_{i} ≤ 10^{9}$) байх ба $i$-р нүдэнд бичигдсэн тоо юм. Нүднүүд дахь тоонууд нь $1$-с $n$ хүртэлх дарааллаар өгөгдөнө. $a_{i}$ тоонууд нь тэнцүү байж болно.

Гаралт

Эхний мөрөнд хамгийн бага хугацааны нэгжийн тоо болох $t$ тоог хэвлэ.

Дараагийн $n$ мөрүүдийн мөр бүрт роботын хөдөлгөөний чиглэл болон уг чиглэлд хэдэн нүд явахыг илэрхийлнэ. Хөдөлснийхөө дараа робот ирсэн нүднийхээ тоог бичиж авна. Чиглэл болон явах нүдний тоо нь цагийн зүүний дагуу $x$ ($0 ≤ x ≤ n - 1$) нүд явах тохиолдолд $+x$ хэлбэрээр харин цагийн зүүний эсрэг $x$ нүд явах тохиолдолд $-x$ хэлбэрээр бичигдэнэ.

$x$-ийн утгуудын тэмдэг харгалзахгүй нийлбэр нь $t$-тэй тэнцүү байх ёстой.

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

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

Оролт
9 1
0 1 2 2 2 1 0 1 1
Гаралт
12
+0
-3
-1
+2
+1
+2
+1
+1
+1
Оролт
8 1
0 1 0 1 0 1 0 1
Гаралт
13
+0
+2
+2
+2
-1
+2
+2
+2
Оролт
8 1
1 2 3 4 5 6 7 8
Гаралт
7
+0
+1
+1
+1
+1
+1
+1
+1
Оролт
8 1
0 0 0 0 0 0 0 0
Гаралт
7
+0
+1
+1
+1
+1
+1
+1
+1
Сэтгэгдлүүдийг ачааллаж байна...