E. Антон ба Ира

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

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

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

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

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

Бидэнд $1$-ээс $n$ хүртэлх тоог агуулсан $p$ болон $s$ хоёр дараалал байна. Бид $p_{i}$ элементийг $p_{j}$ элементтэй $|i - j|$ зоосоор байрыг нь сольж чадна. $p$ дарааллаас $s$ дарааллыг үүсгэхэд шаардагдах зоосны хамгийн бага хэмжээг олж хэвлэ. Мөн энэ шийдлийг гүйцэтгэхэд шаардлагатай солих үйлдлүүдийг хэвлэ.

Оролт

Эхний мөрөнд дарааллын урт болох $n$ ($1 ≤ n ≤ 2000$) тоо байна.

Хоёр дахь мөрөнд $1$-ээс $n$ тоог агуулсан $p$ дараалал байна. $1$-ээс $n$ хүртэлх тоо бүр дараалалд ганц ширхэг л байна.

Гурав дахь мөрөнд $1$-ээс $n$ тоог агуулсан $s$ дараалал байна. $1$-ээс $n$ хүртэлх тоо бүр дараалалд ганц ширхэг л байна.

Гаралт

Эхний мөрөнд $p$ дарааллаас $s$ дарааллыг үүсгэхэд шаардлагатай зоосны хамгийн бага тоон утгыг хэвлэнэ.

Хоёр дахь мөрөнд шаардлагатай үйлдлүүд(солилцоонууд)-ийн тоо $k$-г ($0 ≤ k ≤ 2*10^{6}$) хэвлэнэ.

Дараагийн $k$ мөрөнд үйлдлүүдийг хэвлэ. Мөр бүр хоёр бүхэл тоон утга агуулах ба $i$ болон $j$ ($1 ≤ i, j ≤ n$, $i ≠ j$) байна. Эдгээр нь $p_{i}$ болон $p_{j}$ хоёрыг хооронд нь солино гэдгийг илэрхийлнэ.

Энэ нь шийдэл байгаа гэдгийг батлана.

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

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

Оролт
4
4 2 1 3
3 2 4 1
Гаралт
3
2
4 3
3 1

Тэмдэглэл

Эхний жишээн дээр бид 3 болон 4-р байрлалд байгаа элементүүдийг солих ба $p$ дараалал 4 2 3 1 хэлбэртэй болно. Бид энэ үйлдэлд $|3 - 4| = 1$ зоос төлнө. Дараа нь 1 болон 3-р байрлалд байгаа элементүүдийг солих ба дараалал $3241$ болж $s$-тэй тэнцэнэ. Бид энэ үйлдэлд $|3 - 1| = 2$ зоос төлнө. Ингээд нийт гурван зоос төлнө.

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