D. Валера ба солилтууд

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

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

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

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

$n$ урттай $p$ сэлгэмэл нь $p_{1}, p_{2}, ..., p_{n}$ $(1 ≤ p_{i} ≤ n)$ ялгаатай бүхэл тоонуудын дараалал юм. Хэрвээ ямар ч $i$ нь дараах $p_{i} = i$ тэнцэтгэлийг хангадаг бол сэлгэмэл нь өвөрмөц сэлгэмэл юм.

$(i, j)$ солилт гэдэг нь сэлгэмэлийн $p_{i}$ ба $p_{j}$ элементүүдийг солих үйлдэл юм. $f(p)$ бол $p$ сэлгэмэлийг өвөрмөц сэлгэмэл болгоход хэрэгтэй хамгийн бага солилтын тоо гэж үзье.

Валера $f(q) = m$ байхаар $p$ сэлгэмэлийг ямар нэг $q$ сэлгэмэл рүү хамгийн бага солилт ашиглан хэрхэн өөрчлөхийг бодов. Үүнийг шийдэхэд нь түүнд тусал.

Оролт

Эхний мөр нь $p$ сэлгэмэлийн урт болох $n$ ($1 ≤ n ≤ 3000$) бүхэл тоог агуулна. Дараагийн мөрөнд Валерагийн анхны сэлгэмэл болох $n$ ширхэг ялгаатай бүхэл тоо $p_{1}, p_{2}, ..., p_{n}$ ($1 ≤ p_{i} ≤ n$) байна. Хамгийн сүүлийн мөр нь $m$ ($0 ≤ m < n$) бүхэл тоог агуулна.

Гаралт

Эхний мөрөнд солилтын хамгийн бага тоо $k$ бүхэл тоог хэвлэнэ.

Хоёр дахь мөрөнд $2k$ бүхэл тоонууд $x_{1}, x_{2}, ..., x_{2k}$ хэвлэнэ. Солисон дарааллын тодорхойлолт. Хэвлэсэн тоо нь дараалан солилт хийснийг харуулна. $(x_{1}, x_{2})$, $(x_{3}, x_{4})$, ..., $(x_{2k - 1}, x_{2k})$.

Хэрвээ хамгийн бага урттай олон дарааллын солилт байгаа бол цагаан толгойн дарааллаар хамгийн багийг хэвлэнэ.

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

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

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

Тэмдэглэл

Дараалал $x_{1}, x_{2}, ..., x_{s}$ нь цагаан толгойн дарааллын хувьд $y_{1}, y_{2}, ..., y_{s}$ дарааллаас бага, Хэрвээ $r$ $(1 ≤ r ≤ s)$ бүхэл тоо бол $x_{1} = y_{1}, x_{2} = y_{2}, ..., x_{r - 1} = y_{r - 1}$ , $x_{r} < y_{r}$ байна.

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