# PBinfo #1639 – Secvente3 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Considerăm şirul de numere naturale nenule  distincte  \(a_1, a_2, …, a_N\). Notăm cu \(L_i\) lungimea maximă a unei secvențe de elemente cu valori consecutive care se poate obţine prin ordonarea crescătoare a primelor i elemente din şirul dat. De exemplu, pentru șirul 7, 2, 3, 8, 20, 4, 10, 9  avem: \(L_1 = 1, L_2 = 1, L_3 = 2, L_4 = 2, L_5 = 2, L_6 = 3, L_7 = 3, L_8 = 4\).

Cerința
Să se determine \(L_1, L_2, …, L_N\).

Date de intrare
Fişierul secvente.in conţine pe prima linie numărul natural N. Pe fiecare din următoarele N linii se găseşte câte un număr natural, deci pe linia i+1 se va afla elementul \(a_i\), pentru i=1...N. 

Date de ieșire
Fişierul secvente.out conţine exact N linii. Pe linia i (i = 1...N) se va afișa valoarea \(L_i\).

Restricții și precizări

3 ≤ N ≤ 200.000
1 ≤ \(a_i\) ≤ 1.000.000, pentru orice i = 1...N
Pentru 35% din teste se garantează că  N ≤ 1.000

Exemplu:
secvente.in

8
7
3
2
8
20
4
10
9
secvente.out

1
1
2
2
2
3
3
4 
Explicație
\(L_1\). Șirul: 7. Lungime maximă 1.
\(L_2\). Șirul: 7, 3. Lungime maximă 1.
\(L_1\). Șirul: 7, 3, 2. Şirul sortat este 2, 3, 7. Lungimea maximă este 2 (dată de secvenţa 2, 3).
\(L_4\). Șirul: 7, 3, 2, 8. Lungime maximă 2 (dată de 2, 3) 
\(L_5\). Șirul: 7, 3, 2, 8, 20. Lungime maximă 2 (dată de 2, 3).
\(L_6\). Șirul: 7, 3, 2, 8, 20, 4. Şirul sortat este 2, 3, 4, 7, 8, 20. Lungimea maximă este 3 (dată de secvenţa 2, 3, 4). 
\(L_7\). Șirul: 7, 3, 2, 8, 20, 4, 10. Lungime maximă 3 (dată de 2, 3, 4).
\(L_8\). Șirul: 7, 3, 2, 8, 20, 4, 10, 9. Şirul sortat este 2, 3, 4, 7, 8, 9, 10, 20. Lungimea maximă este 4 (dată de secvenţa 7, 8, 9, 10).

## Cod sursă C++

```cpp
#define TuTTy "Cosmin-Mihai Tutunaru"
#include <cstdio>
#include <cassert>
#include <vector>
#include <algorithm>
#define infile "secvente.in"
#define outfile "secvente.out"
#define nMax 200013
#define vMax 1000013
using namespace std;
bool vz[vMax];
int v[nMax];
int pos[vMax];
int n;
void read() {
    scanf("%d\n", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &v[i+1]);
        assert(vz[v[i+1]] == false);
        vz[v[i+1]] = true;
    }
}
void solve() {
    int best = 0;
    for (int i = 1; i <= n; ++i) {
        int begin = v[i], end = v[i];
        if (pos[v[i]-1]) begin = pos[v[i]-1];
        if (pos[v[i]+1]) end = pos[v[i]+1];
        pos[begin] = end;
        pos[end] = begin;
        best = max(best, end - begin + 1);
        printf("%d\n", best);
    }
}
int main() {
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);
    read();
    solve();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1639)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1639/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1639/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)