E. Дарааллын хамгийн урт өсөх дэд дараалал

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

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

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

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

Дараагийн "Өгөгдлийн бүтэц ба алгоритм" хичээл хамгийн урт өсөх дэд дарааллын талаар байх болно. Илүү сайн ойлгохын тулд Наам хичээлээс хэд хоногийн өмнө түүнийг сурахаар шийдсэн байна.

Наам $n$ ($1 ≤ n ≤ 10^{5}$) ширхэг $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{5}$) элементүүдээс бүрдсэн $a$ дараалал үүсгэв. Хэрвээ $a_{i_{1}} < a_{i_{2}} < a_{i_{3}} < ... < a_{i_{k}}$ бол $1 ≤ i_{1} < i_{2} < ... < i_{k} ≤ n$ байх $a_{i_{1}}, a_{i_{2}}, ..., a_{i_{k}}$ дэд дарааллыг өсөх дараалал гэнэ. Бүх өсөх дэд дарааллууд дундаас хамгийн их урттайг нь хамгийн урт өсөх дэд дараалал гэнэ.

Магадгүй хэд хэдэн хамгийн урт өсөх дэд дараалал байж болно гэдгийг Наам ойлгосон байна. Тиймээс тэр бүх $i$ ($1 ≤ i ≤ n$) индексүүдийг гурван бүлэгт хуваасан:

  1. $a_{i}$ нь хамгийн урт өсөх дэд дараалалд хамаарахгүй байх бүх $i$-н бүлэг.
  2. $a_{i}$ нь хамгийн урт өсөх дэд дараалалд бүгдэд нь хамаарахгүй ч ядаж нэг удаа хамаарах бүх $i$-н бүлэг.
  3. $a_{i}$ нь хамгийн урт өсөх дэд дараалал бүрд хамаарах бүх $i$-н бүлэг.

$a$-н хамгийн урт өсөх дэд дараалалын тоо нь маш их байж болох ба ангилах үйлдэл хэцүү байх болно. Таны даалгавар бол энэ ажлыг дуусгахад түүнд туслах юм.

Оролт

Эхний мөр нь $a$ дарааллын элементүүдийн тоог илэрхийлсэн $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоог агуулна.

Хоёр дахь мөр нь зайгаар тусгаарлагдсан $n$ ширхэг $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 10^{5}$) бүхэл тоонуудаас бүрдэнэ.

Гаралт

$n$ тэмдэгтүүд агуулсан тэмдэгт мөр хэвлэнэ. $i$-р тэмдэгт нь дээр дурьдсан бүлгүүд дундах $i$ индексээс хамаарч '$1$', '$2$' эсвэл '$3$' байх ёстой.

Орчуулсан: Даариймаа

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

Оролт
1
4
Гаралт
3
Оролт
4
1 3 2 5
Гаралт
3223
Оролт
4
1 5 2 3
Гаралт
3133

Тэмдэглэл

Хоёр дахь жишээнд $a$ дараалал 4 элементээс бүрдэнэ: ${a_{1}, a_{2}, a_{3}, a_{4}}$ = ${1, 3, 2, 5}$. $a$ дараалалд 3 урттай яг 2 ширхэг хамгийн урт өсөх дэд дараалал байгаа, тэдгээр нь: ${a_{1}, a_{2}, a_{4}}$ = ${1, 3, 5}$ ба ${a_{1}, a_{3}, a_{4}}$ = ${1, 2, 5}$.

Гурав дахь жишээнд $a$ дараалал 4 элементээс бүрдэнэ: ${a_{1}, a_{2}, a_{3}, a_{4}}$ = ${1, 5, 2, 3}$. $a$ дараалалд 3 урттай яг 1 ширхэг хамгийн урт өсөх дэд дараалал байгаа, энэ нь ${a_{1}, a_{3}, a_{4}}$ = ${1, 2, 3}$.

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