Rezolvare PBinfo #3729

Se consideră doi vectori care conțin numere naturale: s cu M elemente și v cu N elemente. Numim secvență i-exclusivă o secvență a vectorului s care nu conține niciuna dintre valorile v[1], v[2], …, v[i].

Cerința

Scrieți un program care să determine, pentru orice 1 ≤ i ≤ N, lungimea maximă a unei secvențe i-exclusive.

Date de intrare

Fișierul de intrare exclusiv.in conține pe prima linie numerele naturale M și N. Pe linia a doua se află M numere naturale reprezentând elementele vectorului s, iar pe linia a treia N numere naturale reprezentând elementele vectorului v. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire exclusiv.out va conține N linii. Pe linia i (1 ≤ i ≤ N) va fi scris un număr natural care reprezintă lungimea maximă a unei secvențe i-exclusive.

Restricții și precizări

• 1 ≤ N ≤ 2.000
• 3 ≤ M ≤ 100.000
• Vectorii s și v conțin numere naturale mai mici sau egale cu 2.000.000.000, memorate începând cu poziția 1
• Valorile din fiecare vector nu sunt obligatoriu distincte două câte două.
• O subsecvență nevidă în s este formată din elemente situate pe poziții consecutive (s[i], s[i + 1], …, s[j]), i ≤ j. O subsecvență i-exclusivă poate fi și vidă, lungimea ei fiind 0.

Exemplu:

exclusiv.in

20 6
11 5 11 7 2 10 11 9 2 77 88 88 88 2 7 2 2 77 2 11 
11 5 7 9 5 2

exclusiv.out

12
12
7
6
6
4

Explicație

Cea mai lungă secvență 1-exclusivă (care nu conține valoarea 11) este 9 2 77 88 88 88 2 7 2 2 77 2 și are lungimea 12.
Cea mai lungă secvență 2-exclusivă (care nu conține valorile 11 și 5) este 9 2 77 88 88 88 2 7 2 2 77 2 și are lungimea 12.
Cea mai lungă secvență 3-exclusivă (care nu conține valorile 11, 5 și 7) este 9 2 77 88 88 88 2 și are lungimea 7.
Cea mai lungă secvență 4-exclusivă (care nu conține valorile 11, 5, 7 și 9) este 2 77 88 88 88 2 și are
lungimea 6.
Cea mai lungă secvență 5-exclusivă (care nu conține valorile 11, 5 7, 9 și 5) este 2 77 88 88 88 2 și are lungimea 6.
Cea mai lungă secvență 6-exclusivă (care nu conține valorile 11, 5, 7, 9, 5 și 2) este 77 88 88 88 și are lungimea 4.