F. Шинэ жилийн мод

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

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

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

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

Та бол мэргэжлийн программер ба танд шинэ жилийн мод гэж $4$-н оройтой нэг оройн зэрэг нь $3$ ба энэ нь $1$ дугаартай, мөн үүнд холбогдсон $2$, $3$, $4$ дугаартай навчнуудтай.

Шинэ жилээр программерууд ихэвчлэн хөгжилддэг. Та энэ модонд орой нэмж зугаацах гэж байгаа. Орой нэмэх үйлдэл нь дараах загвартай: - Эхлээд модноос ямар нэгэн $v$ дугаартай навч сонгоно. - Энэ үед модонд $n$ орой байсан гэж үзье. Тэгвэл та $v$ болон $n+1$ оройн хооронд мөн $v$ болон $n+2$ оройн хооронд ирмэг үүсгэнэ.

Таны даалгавар бол модонд орой нэмэх орой хийсний дараах модны диаметрийг хэвлэнэ.

Оролт

Эхний мөрөнд хийгдэх үйлдлийн тоо $q\ (1\ ≤\ q\ ≤\ 5·10^5)$ өгөгдөнө. Дараагийн $q$ мөрөнд $v_i\ (1\ ≤\ v_i\ ≤\ n)$ буюу ирмэг нэмэх оройн дугаар байна. Тухайн үеийн модны оройн тоог $n$ байсан гэж үзнэ.

Гаралт

$q$ мөрөнд үйлдэл хийгдэсний дараах модны диаметрийг хэвлэнэ.

Орчуулсан: Говьхүү

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

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