1048 - Schi

La proba de sărituri cu schiurile din cadrul jocurilor olimpice de iarnă participă N concurenți, numerotați cu numere de la 1 la N.

Regulile de desfășurare a probei sunt următoarele:

• concurenții evoluează pe rând, în ordine de la 1 la N;
• fiecare concurent va efectua o singură săritură;
• după efectuarea săriturii fiecare concurent primește un anumit punctaj;
• pe tot parcursul concursului, comisia de arbitri are obligația să alcătuiască o listă cu punctajele obținute de concurenți, în ordinea evoluției lor;
• evoluția unui concurent durează exact un minut;
• nu se face pauză între evoluțiile a doi concurenți care au numere de ordine consecutive;
• afișarea punctajului nu necesită timp suplimentar după efectuarea săriturii;
• proba se încheie la un minut după evoluția ultimului concurent.

Pe tot parcursul concursului se ține în mod neoficial și un clasament parțial, pe baza rezultatelor obținute de concurenții care au evoluat până în acel moment. Asta pentru că șeful comisiei de arbitri are o curiozitate aparte și pune K întrebări sub forma următoare: Câte minute s-a ocupat primul loc din clasament cu un punctaj egal cu X puncte? Dacă nici un concurent nu s-a clasat pe primul loc cu X puncte atunci primește ca răspuns valoarea 0.

Cerința

Scrieți un program care determină răspunsul pentru fiecare dintre cele K întrebări puse de șeful comisiei de arbitri.

Date de intrare

Fișierul de intrare schi.in conține pe prima linie un număr natural, N reprezentând numărul de concurenți. Pe a doua linie a fișierului sunt scrise cele N numere naturale separate prin câte un spațiu, reprezentând punctajele obținute de fiecare dintre cei N concurenți, în ordinea în care aceștia au evoluat. Pe a treia linie a fișierului este scris numărul natural K ce reprezintă numărul de întrebări puse de șef. Pe a patra linie a fișierului sunt scrise K numere naturale separate prin câte un spațiu, reprezentând valorile X ale punctajelor alese de șeful comisiei de arbitri.

Date de ieșire

Fișierul de ieșire schi.out va conține pe prima linie K numere, separate prin câte un spațiu, reprezentând, în ordine, răspunsurile la cele K întrebări.

Restricții și precizări

• 1 ≤ N ≤ 100 000
• 1 ≤ K ≤ 100 000
• 0 ≤ punctajele obținute de concurenți ≤ 1 000 000 000
• 0 ≤ valorile X alese de șeful arbitrilor ≤ 1 000 000 000

Exemplu:

schi.in

10
1 6 5 3 6 8 8 6 1 9
6
5 1 6 8 2 9

schi.out

0 1 4 4 0 1

Explicație

Cu punctajul 5 nu s-a ocupat niciodată locul 1, cu punctajul 1 s-a ocupat primul loc un singur minut, cu punctajele 6 și 8 s-a ocupat locul 1 câte 4 minute. Cu punctajul 2 nu s-a ocupat locul 1. El nici nu a fost obținut de vreun concurent. Cu punctajul 9 s-a ocupat locul 1 un minut.

Încărcare soluție

Lipește codul aici

import sys

DIM = 100010
v = [0] * DIM
n = 0
i = 0
T = 0
st = 0
dr = 0
x = 0
q = 0
maxim = 0

def cautMinim(x):
    p = 1
    u = n
    mid = 0
    while p <= u:
        mid = (p + u) // 2
        if x <= v[mid]:
            u = mid - 1
        else:
            p = mid + 1
    if v[p] == x:
        return p
    else:
        return -1

def cautMaxim(x):
    p = 1
    u = n
    mid = 0
    while p <= u:
        mid = (p + u) // 2
        if x >= v[mid]:
            p = mid + 1
        else:
            u = mid - 1
    if v[u] == x:
        return u
    else:
        return -1

if __name__ == "__main__":
    fin = open("schi.intxt", "r")
    fout = open("schi.outtxt", "w")
    n = int(fin.readline())
    maxim = -1
    for i in range(1, n+1):
        x = int(fin.readline())
        if x > maxim:
            maxim = x
        v[i] = maxim
    q = int(fin.readline())
    for i in range(1, q+1):
        x = int(fin.readline())
        st = cautMinim(x)
        if st == -1:
            fout.write("0 ")
        else:
            dr = cautMaxim(x)
            fout.write(str(dr - st + 1) + " ")

    fin.close()
    fout.close()