Rezolvare PBinfo #4053

Cerința

Se dă o un șir \(p\) de \(n\) numere distincte din mulțimea \({1, 2, \dots, n}\). Separați șirul într-un număr minim de subsecvențe astfel încât după o reordonare a acestora se poate obține șirul \([1, 2, \dots, n]\).

Date de intrare

Se citește numărul \(n\), iar apoi \(n\) numere naturale, separate prin spații.

Date de ieșire

Se afișează \(n\) numere naturale între \(1\) și \(n\). Al \(i\)-lea număr reprezintă subsecvența din care face parte elementul \(p_i\). Subsecvențele trebuie numerotate cu numere consecutive începând de la \(1\), în ordine de la stânga la dreapta.

Restricții și precizări

• \(1 \le n \le 10^5\)

Exemplu:

Intrare

6
6 3 4 5 1 2

Ieșire

1 2 2 2 3 3

Explicație

Șirul se separă în subsecvențele \([6 ]\), \([3,4,5]\) și \([1,2]\). Această se reordonează în următorul mod: \([1, 2]\), \([3,4,5]\), \([6 ]\).