B. Өлсгөлөн цуваа

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

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

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

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

Иахуб ба Иахубина тансаг ресторанд болзохоор болжээ. Тооцоо хийх хүртэл бүх зүйл хэвийн байлаа. Хмм та ер нь юу болсныг ойлгож байгаа биз дээ тээ. Зөөгч Иахубаас $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$ байх ёстойг анхаарна уу) тоонууд. Энэ тоонууд "Өлсгөлөн цуваа" байх ёстой.

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

Орчуулсан: gmunkhbaatarmn

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

Оролт
3
Гаралт
2 9 15
Оролт
5
Гаралт
11 14 20 27 31
Сэтгэгдлүүдийг ачааллаж байна...