B. Зума

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

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

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

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

Женос саяхан утсандаа Зума тоглоомыг суулгасан. Зума тоглоомонд $n$ үнэт чулуутай шулуун байх ба эдгээрийн $i$-р чулуу бүр $c_{i}$ өнгөтэй. Тоглоомын зорилго нь шулуунд байгаа бүх үнэт чулууг боломжит хамгийн хурданаар устгах юм.

Нэг секундэд Женос өнгөт чулуунуудаас яг нэг үргэлжилсэн палиндром дэд тэмдэгт мөрийг сонгож шулуунаас устгах боломжтой. Дэд тэмдэгт мөр устсаны дараа үлдсэн чулуунууд нэгдэж дахин чулуун шулууныг үүсгэнэ. Шулууныг бүхэлд нь устгахад хамгийн багадаа хэдэн секунд шаардлагатай вэ?

Палиндром гэж нэрлэгдэх тэмдэгт мөр (эсвэл дэд тэмдэгт мөр) нь урдаас болон хойноос нь уншихад ижил уншигддаг тэмдэгт мөр гэдгийг санаарай. Бидний тохиолдолд энэ нь эхний чулууны өнгө сүүлийнхтэй ижил ба хоёр дахь чулууны өнгө сүүлийн чулууны наад талын чулууныхтай ижил гээд үргэлжилнэ гэсэн үг.

Оролт

Оролтын эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 500$) байх ба үнэт чулуунуудын тоо.

Хоёр дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоон утга $c_{i}$ ($1 ≤ c_{i} ≤ n$) байх ба шулуун дахь $i$-р үнэт чулууны өнгө байна.

Гаралт

Шулууныг бүхэлд нь устгахад хамгийн багадаа хэдэн секунд шаардагдахыг олж түүнийг илэрхийлэх бүхэл тоон утгыг хэвлэ.

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

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

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

Тэмдэглэл

Эхний жишээн дээр Женос шулууныг бүхэлд нь нэг секундэд устгаж чадна.

Хоёр дахь жишээн дээр Женос нэг секундэд нэг л үнэт чулуу устгаж чадна ингээд гурван үнэт чулууг гурван секундэд устгана.

Гурав дахь жишээн дээр хамгийн тохиромжтой цаг болох хоёр секундэд устгахын тулд эхлээд $4 4$ палиндромыг устгаад тэгээд $1 2 3 2 1$ палиндромыг устгана.

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