Rezolvare PBinfo #2510

Considerăm un șir de numere naturale nenule a[1], a[2], …, a[n]. În acest șir o V-secvență este o secvență maximală de forma a[x], a[x+1], …, 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ța

Pentru un șir de numere dat, trebuie să răspundeți la Q întrebări notate V[1], V[2],…, 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],…, 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 ≤ toate numerele din fișierul de intrare ≤ 1 100 000
• Pentru teste totalizând 75 puncte, 1 ≤ toate numerele din fișierul de intrare ≤ 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.