Иахуб ба Иахубина тансаг ресторанд болзохоор болжээ. Тооцоо хийх хүртэл бүх зүйл хэвийн байлаа. Хмм та ер нь юу болсныг ойлгож байгаа биз дээ тээ. Зөөгч Иахубаас $n$ ширхэг тооноос бүтсэн "Өлсгөлөн цуваа" бичиж чадвал мөнгө авахгүй гэжээ.

$n$ ширхэг тооноос бүтсэн $a_1$, $a_2$, ..., $a_n$ дараалал дараах нөхцлүүдийг хангаж байвал "Өлсгөлөн цуваа" болно:

• Элементүүд өсөх дарааллаар байрласан байх. Өөрөөр хэлбэл $a_i < a_j$ ($1 ≤ i < j ≤ n$) нөхцөл биелэнэ гэсэн үг.
• Аль ч хоёр $i$, $j$ ($i < j$) дугаарын хувьд $a_j$ нь $a_i$-д хуваагдахгүй байх.

Иахуб асуудлыг эвгүй нөхцөл байдлаар мултрахын тулд танаас тусламж хүсчээ. Түүнд $n$ элементтэй "Өлсгөлөн цуваа"-г олж өгнө үү.

Оролт

$n$ бүхэл тоо ($1 ≤ n ≤ 10^5$).

Гаралт

Зайгаар тусгаарлагдсан $n$ ширхэг $a_1$, $a_2$, ..., $a_n$ ($1 ≤ a_i ≤ 10^7$ байх ёстойг анхаарна уу) тоонууд. Энэ тоонууд "Өлсгөлөн цуваа" байх ёстой.

Олон хариу байвал алийг нь ч хэвлэсэн болно.