!>problema/expanding?poza_expand2.png!
În Ţinutul Ooo, Finn şi Jake descoperă un şir magic de pietre strălucitoare aşezate în linie.

Fiecare piatră are o valoare, valori pe care le vom reprezenta cu un sir $a$ de $n$ elemente.
In mod important, nu exista 3 pietre care sa aiba aceeasi valoare.
Incercand sa colecteze toate pietrele, cei doi se vor misca dupa urmatoarele reguli:
 
- ei pornesc la o pozitie $p$, cu o potiune de putere $c = a{~p~}$.
- la un pas, ei se pot muta doar intr-o pozitie adiacenta, daca aceasta exista in sir, aceasta putand fi vizitata sau nu anterior.
- pentru un ban, ei pot schimba puterea potiunii $c$ la orice valoare pozitiva.
- o mutare intr-o pozitie vizitata este mereu posibila si nu are niciun efect
- pentru a vizita o pozitie nevizitata, trebuie sa aiba puterea potiunii $c$ egala cu valoarea pozitiei in care merg.
- cand ajung intr-o pozitie noua, ei colecteaza piatra din acea pozitie.

Fiecare piatră are o valoare, valori pe care le vom reprezenta cu un şir a de n elemente.
În mod important, nu există trei pietre care să aibă aceeaşi valoare.

Definim $f(p)$ ca fiind numarul minim de bani de care au nevoie cei doi pentru a putea colecta toate pietrele, daca pornesc in pozitia $p$ cu $c = a{~p~}$.

Încercând să colecteze toate pietrele, cei doi se vor mişca după următoarele reguli:

Vi se dau $n$, sirul $a$ de $n$ elemente si $q$ query-uri, la fiecare primind o pozitie $p$ si trebuind sa afisati $f(p)$.

Ei pornesc de la o poziţie p, cu o poţiune de putere c = a[p].
La un pas, ei se pot muta doar într-o poziţie adiacentă; dacă aceasta există în şir, poate fi vizitată sau nu anterior.
 
Pentru un ban, ei pot schimba puterea poţiunii c la orice valoare pozitivă.
 
O mutare într-o poziţie vizitată este mereu posibilă şi nu are niciun efect.
 
Pentru a vizita o poziţie nevizitată, trebuie ca puterea poţiunii c să fie egală cu valoarea poziţiei în care merg.
 
Când ajung într-o poziţie nouă, ei colectează piatra din acea poziţie.
 
Definim f(p) ca fiind numărul minim de bani de care au nevoie cei doi pentru a putea colecta toate pietrele, dacă pornesc în poziţia p cu c = a[p].
 
Vi se dau n, şirul a de n elemente şi q query-uri; pentru fiecare query primiţi o poziţie p şi trebuie să afişaţi f(p).

h2. Date de intrare
Fişierul de intrare $expanding.in$ conţine pe prima linie numărul $n$, urmat pe a doua linie de şirul $a$.