E. Дэд мөрийг устгах

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

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

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

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

Бяцхан R "Дэд мөрийг устгах" нэртэй тоглоом тоглож байна. Энэ тоглоомонд $w$ бүхэл тоонуудаас бүрдсэн дараалал өгөгдсөн ба та дарааллыг өөрчилж оноо авч чадна. Өөрчлөлт нь ганцхан төрөл бөгөөд зөвхөн тэмдэгт мөрийн дэд мөрийг л устгаж чадна. Илүү тодорхой хэлвэл, та $w$-н хэд хэдэн үргэлжилсэн элементийг сонгож чадах ба дарааллаас тэдгээр элементээ устгана. $w_{l}, w_{l + 1}, ..., w_{r}$-г дарааллаас сонгосон элементүүд гэж үзье. Эдгээр нь дараах нөхцлийг хангах ёстой:

  • $(l ≤ i < r)$ байх дурын $i$-н хувьд $|w_{i} - w_{i + 1}| = 1$ тэнцэтгэл үнэн байна;
  • $(l ≤ i < r)$ байх дурын $i$-н хувьд $2*w_{i} - w_{i + 1} - w_{i - 1} ≥ 0$ тэнцэтгэл биш үнэн байх ёстой.

$w$-с сонгосон дэд мөрийг устгасны дараа та $v_{r - l + 1}$ оноо авна. Тодорхойлсон үйлдлийг хэд хэдэн удаа гүйцэтгэж болох бөгөөд энэ тохиолдолд тохирох дэд мөр байна. Мөн та тоглоомыг хэзээ ч дуусгаж болно. Таны даалгавар бол тоглоомоос авж чадах хамгийн их оноог тооцоолох юм.

Оролт

Эхний мөрөнд $w$ дарааллын анхны урт болох $n$ $(1 ≤ n ≤ 400)$ бүхэл тоог оруулна. Дараагийн мөрөнд үйлдлүүдийн өртөг болох $n$ ширхэг бүхэл $v_{1}, v_{2}, ..., v_{n}$ $(0 ≤ |v_{i}| ≤ 2000)$ тоонууд байна. Гуравдугаар мөрөнд анхны $w$ дараалалыг тодорхойлох $n$ ширхэг $w_{1}, w_{2}, ..., w_{n}$ $(1 ≤ w_{i} ≤ 10^{9})$ бүхэл тоонууд байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ нь таны авч чадах хамгийн их оноо юм.

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

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

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