B. Вика ба квадратууд

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

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

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

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

Викад ялгаатай өнгийн будагтай $n$ шилэн сав байна. Бүх сав $1$-c $n$ хүртэл дугаарлагдсан ба $i$-р сав $a_{i}$ литр $i$ өнгөтэй будаг агуулсан.

Викад мөн хязгааргүй урттай $1 × 1$ хэмжээтэй квадратуудаас бүрдсэн $1$ өргөнтэй цаас байна. Квадратууд $1$, $2$, $3$ гээд цааш дугаарлагдана. Вика квадратуудыг нэг нэгээр нь зүүнээс баруун тийш, $1$ дугаартай квадратаас эхлээд дурын өнгөөр будаж эхлэхээр шийдсэн. Хэрвээ квадрат $x$ өнгөөр будагдсан байсан бол дараагийн квадрат $x + 1$ өнгөөр будагдсан байх болно. $x = n$ тохиолдолд дараагийн квадрат $1$ өнгөөр будагдана. Хэрвээ Викагийн будахыг хүссэн өнгөтэй будаг одоо байхгүй бол тэр зогсоно.

Квадрат үргэлж зөвхөн нэг өнгөөр будагдах ба $1$ литр будаг хэрэглэнэ. Таны ажил бол хамгийн олон нүд будагдахаар Викагийн эхлэх өнгийг сонгох юм.

Оролт

Оролтын эхний мөрөнд нэг ширхэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 200 000$) байх ба Викад байгаа өнгөтэй савнуудын тоо байна.

Оролтын хоёр дахь мөрөнд бүхэл тоон утгуудын дараалал $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{9}$) байх ба энд $a_{i}$ нь $i$-р саванд хэдэн литр будаг байгаа тоотой тэнцүү, өөрөөр Викад байгаа $i$ өнгөтэй будагны литрийн тоо гэсэн үг.

Гаралт

Гаралтын нэг мөрөнд нэг ширхэг бүхэл тоон утга байх ёстой ба энэ нь хэрвээ Вика дээр тодорхойлсон дүрмүүдийг дагасан бол будаж чадах квадратуудын хамгийн их тоо байна.

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

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

Оролт
5
2 4 2 3 3
Гаралт
12
Оролт
3
5 5 5
Гаралт
15
Оролт
6
10 10 10 1 10 10
Гаралт
11

Тэмдэглэл

Эхний жишээн дээр шилдэг стратеги нь $4$ дугаартай өнгийг ашиглан будаж эхлэх юм. Ингээд квадратууд дараах өнгүүдээр будагдана (зүүнээс баруун): 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.

Хоёр дахь жишээн дээр Вика дурын өнгөөр будаж эхэлж болно.

Гурав дахь жишээн дээр Вика $5$ дугаартай өнгийг ашиглан будаж эхлэх ёстой.

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