!>problema/expanding?poza_expand2.png!

📖 Povestea reformulată în română
 

Î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 (o culoare sau o energie), iar fiecare valoare apare de cel mult două ori în tot şirul.
 
ake, fiind elastic, poate alege o poziţie iniţială p din şir, şi începe o călătorie de extindere:
 
La început:
Intervalul [l, r] = [p, p] (adică doar piatra de la poziţia p).
Jake ţine în lăbuţă energia curentă c = valoarea pietrei de la p.
 
Reguli magice:
 
Jake poate schimba energia c în orice valoare pozitivă, dar asta costă 1 poţiune magică.
 
Dacă în stânga există o piatră cu energia c, atunci Jake poate sări la ea şi l scade cu 1.
 
Dacă în dreapta există o piatră cu energia c, atunci Jake se întinde până la ea şi r creşte cu 1.
 
Scopul aventurii:
Jake vrea să se întindă până acoperă întregul şir de pietre, adică [l, r] = [1, n].
Costul final f(p) este numărul minim de poţiuni magice (schimbări de energie) pe care Jake trebuie să le folosească pentru a reuşi.
 
✨ Sarcina ta
 
Ţi se dă lungimea şirului n.
 
Apoi urmează n numere pozitive (valorile pietrelor, fiecare apărând cel mult de două ori).
 
După aceea primeşti un număr q, adică numărul de încercări pe care Jake le face.
 
Urmează q poziţii iniţiale p.

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~}$.

Pentru fiecare dintre ele, trebuie să spui câte poţiuni magice minime are nevoie Jake ca să se întindă pe tot şirul.

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)$.

Vrei să îţi rescriu şi input-output-ul în stilul poveştii (cu „Jake primeşte un şir de pietre…”, „Jake încearcă din poziţia…”, „Răspunde cu…”) sau păstrăm partea formală (n, array, q, queries) dar doar ambalată în poveste?

h2. Date de intrare