A. Шалгалт

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

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

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

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

Шалгалтыг урт нарийхан өрөөнд авах учраас $n$ оюутнууд нэг эгнээнд дараалан сууна. Багш зэргэлдээ ($i$ болон $i + 1$) дугаартай оюутнуудыг байнга хамт сууж найзууд болсон хэмээн сэжиглэж байгаа ба, хэрвээ тэд шалгалтан дээр хамт суувал бие биедээ баттай туслах болно.

Таны даалгавар бол аль болох олон оюутныг сонгож, зэргэлдээ дугаартай оюутнууд хамт суугаагүй байхаар зохион байгуулах юм.

Оролт

Шалгалт өгөх оюутнуудын тоо болох $n$ ($1 ≤ n ≤ 5000$) бүхэл тоог оруулна.

Гаралт

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

Хоёр дахь мөрөнд $k$ ширхэг $a_{1}, a_{2}, ..., a_{k}$ ($1 ≤ a_{i} ≤ n$) бүхэл тоонуудыг хэвлэх бөгөөд $a_{i}$ бол $i$-р байрлалд суух оюутны дугаар юм. Зэргэлдээх байрлалд зэргэлдээ дугаартай оюутнууд суух ёсгүй. Томъёолбол дараах тэнцэтгэл биш үнэн байх ёстой: $1$-ээс $k - 1$ хүртэлх бүх $i$-н хувьд $|a_{i} - a_{i + 1}| ≠ 1$ байна.

Хэрвээ хэд хэдэн хариулт байгаа бол тэдгээрийн аль нэгийг хэвлэнэ үү.

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

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

Оролт
6
Гаралт
6
1 5 3 6 2 4
Оролт
3
Гаралт
2
1 3
Сэтгэгдлүүдийг ачааллаж байна...