vsecvente

Considerăm un șir de numere naturale nenule $a_1$, $a_2$, $\dots$, $a_n$. În acest șir o V-secvență este o secvență maximală de forma $a_x$, $a_{x+1}$, $\dots$, $a_y$ cu proprietatea că toate numerele din secvență au valori mai mici sau egale cu $V$. Este maximală pentru că nu poate fi extinsă spre stânga sau spre dreapta. De exemplu, șirul $a$ = $2$, $2$, $6$, $4$, $3$, $14$, $7$, $4$, $3$, $36$ are două $7$-secvențe: $2$, $2$, $6$, $4$, $3$ și $7$, $4$, $3$. De asemenea, șirul are trei $4$-secvențe: $2$, $2$; $4$, $3$; $4$, $3$. De notat că $2$, $6$, $4$, $3$ nu este 7-secvență, deoarece poate fi extinsă la capătul său stâng cu numărul $2$.

Cerinţe

Pentru un șir de numere dat, trebuie să răspundeți la $Q$ întrebări notate $V_1$, $V_2$, $\dots$, $V_Q$. Pentru fiecare întrebare $i$, dată prin numărul natural $V_i$, trebuie să aflați câte $V_i$-secvențe sunt în șir.

Date de intrare

Fișierul de intrare vsecvente.in conține pe prima linie numărul natural $N$. Pe a doua linie, separate prin câte un spațiu, se află cele $N$ elemente ale șirului. Pe a treia linie se află un singur număr natural $Q$ reprezentând numărul de întrebări. Pe a patra linie, se află șirul de $Q$ numere naturale $V_1$, $V_2$, $\dots$, $V_Q$, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire vsecvente.out va conține $Q$ linii. Linia a $i$-a va conține numărul de $V_i$-secvențe aflate în șir.

Restricții și precizări

• $1 \leq$ toate numerele din fișierul de intrare $\leq 1 \ 100 \ 000$
• Pentru teste totalizând $75$ puncte, $1 \leq$ toate numerele din fișierul de intrare $\leq 550 \ 000$

Exemplu

vsecvente.in

10
2 2 6 4 3 14 7 4 3 36
3
7 1 4

vsecvente.out

2
0
3

Explicație

Sunt trei întrebări:

• sunt două $7$-secvențe: $2 \ 2 \ 6 \ 4 \ 3$ și $7 \ 4 \ 3$
• nu există nicio $1$-secvență
• există trei $4$-secvențe $2 \ 2$; $4 \ 3$ și $4 \ 3$