Editing 2297 - Gogosi


= Cerința =
La magazinul X sunt <code>N</code> persoane așezate la coadă pentru gogoși. Din cauza aglomerației, managerul vrea să împartă persoanele la mai multe case. Deoarece toată lumea trebuie să vadă gogoșile, înălțimea fiecărei persoane trebuie să fie mai mică sau egală decât înălțimile tuturor celor de după el în coadă lui. Mai mult, dacă persoana <code>i</code> în șirul inițial și persoana <code>j</code> în șirul inițial (<code>i</code> < <code>j</code>) ajung în aceeași coadă, persoană <code>i</code> trebuie să fie înaintea persoanei <code>j</code>.

Dându-se <code>N</code>, numărul de persoane și <code>A[i]</code>, înălțimile persoanelor în ordinea inițială, să se afișeze numărul minim de case pe care managerul trebuie să le deschidă.

= Date de intrare =
În fișierul <code>gogosi.in</code> se află pe prima linie numărul <code>N</code> iar pe a doua line <code>N</code> numere naturale, <code>A[i]</code> reprezentând înălțimea persoanei <code>i</code> din coadă inițială.

= Date de ieșire =
Afișați pe prima linie din fișierul <code>gogosi.out</code> numarul minim de case care trebuie deschise.

= Restricții și precizări =

* <code>1 ≤ N ≤ 10<sup>6</sup></code>
* <code>1 ≤ A[i] ≤ 10<sup>5</sup></code>
* <code>1 ≤ A[i] ≤ 2</code> pentru teste în valoare de ''20'' puncte.
* <code>1 ≤ N ≤ 10<sup>3</sup></code> pentru teste în valoare de alte ''30'' puncte.

= Exemplu: =
<code>gogosi.in</code>
 7
 1 4 2 3 9 7 6
<code>gogosi.out</code>
 3

=== Explicație ===
Numărul minim de case care trebuie deschise este <code>3</code>. Există mai multe variante de a împărți persoanele, una dintre acestea este:

Coada <code>1</code>: <code>i 1 2 5</code> (persoanele din sirul initial) <code>A[i]: 1 4 9</code> (inaltimile lor)

Coada <code>2</code>: <code>i 3 6</code> (persoanele din sirul initial) <code>A[i]: 2 7</code> (inaltimile lor)

Coada <code>3</code>: <code>i 4 7</code> (persoanele din sirul initial) <code>A[i]: 3 6</code> (inaltimile lor)


== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import sys
sys.stdin = open('gogosi.in', 'r')
sys.stdout = open('gogosi.out', 'w')

v = []
n = int(input())
for i in range(n):
    a = int(input())
    l = 0
    r = len(v) - 1
    while l <= r:
        mid = (l + r) // 2
        if v[mid] <= a:
            r = mid - 1
        else:
            l = mid + 1
    if l == len(v):
        v.append(a)
    else:
        v[l] = a

print(len(v))


</syntaxhighlight>