Артемд $n$ эерэг бүхэл тоонуудтай массив байгаа. Артем үүгээр тоглохоор шийдсэн байна. Тоглоом нь $n$ нүүдлээс бүрдэх ба нүүдэл бүр нь дараах маягаар явна:

Артем зарим элементийг массиваас сонгож хасна. Ингэснээр тэр $min(a, b)$ оноо авна, энэ $a$ ба $b$ нь хасагдсан тооны хөрш тоонууд юм. Хэрвээ тухайн тоонд хөрш буюу баруун эсвэл зүүн талд нь тоо байхгүй бол Артем ямар нэгэн оноо авахгүй.

Элемент хассаны дараа хоёр хэсэг болсон массивыг хооронд нь нааж үр дүнд нь гарсан шинэ массиваар Артем үргэлжлүүлэн тоглоно. Боря Артемыг энэ тоглоомоос хамгийн ихдээ хэдэн оноо авч чадах бол гэж бодож байна.

Оролт

Эхний мөр нь нэг бүхэл $n$ $(1 ≤ n ≤ 5*10^{5})$ тоо агуулагдана. Энэ нь массивын элементүүдийн тоо. Дараагийн мөрөнд $n$ ширхэг бүхэл $a_{i}$ $(1 ≤ a_{i} ≤ 10^{6})$ тоонууд агуулагдана. Эдгээр нь массивын элементүүдийн утгууд юм.

Гаралт

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