Towers

Cerință

Avem un șir cu numere naturale nenule. Acestea reprezintă înălțimile unor turnuri așezate unul lângă altul în linie (nu lipite).
Ne punem întrebări de forma: pentru o valoare dată $p$, daca trag orizontale înapoi (spre stânga) de undeva dintre pozițiile $p$ și $p+1$, câte turnuri distincte pot atinge?

Pentru interogarea cu $p=8$ observăm că se consideră atins doar turnul $8$ (chiar dacă anterior este turnul $7$ de aceeași înalțime cu el).

Date de intrare

Fișierul towers.in conține pe prima linie numărul $n$. Pe linia a doua sunt $n$ numere naturale reprezentând înălțimile turnurilor, date în ordinea pozițiilor de la $1$ la $n$.
Pe linia următoare se află numărul de interogări $k$. Pe următoarea linie se află cele $k$ valori $p$ cu semnificația de mai sus.

Date de ieșire

Fișierul towers.out conține pe prima linie $k$ numere, reprezentând răspunsul pentru fiecare interogare, în ordinea în care ele apar în fișierul de intrare.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• $1 \leq k \leq 100 \ 000$;
• Înălțimile turnurilor sunt numere naturale nenule de maxim $9$ cifre.
• $1 \leq p \leq n;$ în cazul $p=n$ considerăm drepte trase de oriunde de după ultimul turn.

Exemplu

towers.in

8
3 2 6 1 4 2 5 5
2
6 8

towers.out

3 2