Expanding

problema/expanding

!>problema/expanding?poza_expand2.png!

În Tărâmul 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 şir $a$ de $n$ elemente. **Nu există trei pietre care să aibă aceeaşi valoare**.
Încercând să colecteze toate pietrele, cei doi se vor mişca după următoarele reguli:

Î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.

* Ei pornesc la o poziţie $p$, cu o poţiune de putere $c = a{~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~}$.

* La un pas, ei se pot muta doar într-o poziţie adiacentă, dacă aceasta există în şir, aceasta putând fi vizitată sau nu anterior.
 
* O mutare într-o poziţie vizitată anterior este mereu posibilă şi nu are niciun efect.
 
* Pentru a vizita o poziţie nevizitată, trebuie să aibă puterea poţiunii $c$ egală cu valoarea poziţiei în care merg.
 
* Pentru un ban, ei pot schimba puterea poţiunii $c$ la orice valoare pozitivă.
 
* 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 cele $n$ pietre, dacă pornesc în poziţia $p$ cu $c = a{~p~}$.
 
Se dau $n$, şirul $a$ de $n$ elemente şi $q$ query-uri; pentru fiecare primiţi o poziţie $p$ şi trebuie să afişaţi $f(p)$.

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

h2. Date de intrare

* $1 ≤ p ≤ n$
|_. #  |_. Punctaj |_. Restricţii |

| 1 | 8 | $n ≤ 500$ şi $q ≤ 500$ |
| 2 | 9 | $n ≤ 5000$ şi $q ≤ 10$ |

| 1 | 10 | $n ≤ 500$ şi $q ≤ 500$ |
| 2 | 10 | $n ≤ 5000$ şi $q ≤ 10$ |

| 3 | 15 | $n ≤ 5000$ şi $q ≤ 5000$ |

| 5 | 27 | $n ≤ 100 000$ şi $q ≤ 10$ |
| 5 | 18 | $n ≤ 100 000$ şi $q ≤ 100 000$ |
| 6 | 23 | $n ≤ 1 000 000$ şi $q ≤ 1 000 000$ |

| 5 | 15 | $n ≤ 100 000$ şi $q ≤ 10$ |
| 5 | 25 | $n ≤ 100 000$ şi $q ≤ 100 000$ |
| 6 | 25 | $n ≤ 1 000 000$ şi $q ≤ 1 000 000$ |

h2. Exemplu

table(example). |_. expanding.in |_. expanding.out |

table(example). |_. sandwich.in |_. sandwich.out |

| 8
2 1 3 4 6 3 2 1
8

h3. Explicaţie

$f(1) = 7$. Un şir de mutări posibil este:
 
|_. Poziţie  |_. Poţiune |_. Cost|
| 1 | 2 | Costul iniţal este 0 |
| 1 | 1 | 1 (am schimbat poţiunea din 2 în 1) |
| 2 | 1 | 1 |
| 2 | 3 | 2 (am schimbat poţiunea din 1 în 3) |
| 3 | 3 | 2 |
| 3 | 4 | 3 (am schimbat poţiunea din 3 în 4) |
| 4 | 4 | 3 |
| 4 | 6 | 4 (am schimbat poţiunea din 4 în 6) |
| 5 | 6 | 4 |
| 5 | 3 | 5 (am schimbat poţiunea din 6 în 3) |
| 6 | 3 | 5 |
| 6 | 2 | 6 (am schimbat poţiunea din 3 în 2) |
| 7 | 2 | 6 |
| 7 | 1 | 7 (am schimbat poţiunea din 2 în 1) |
| 8 | 1 | 7 |
 
 
$f(4) = 5$. Un şir de mutări posibil este:
 
|_. Poziţie  |_. Poţiune |_. Cost|
| 4 | 4 | Costul iniţal 0 |
| 4 | 6 | 1 (am schimbat poţiunea din 4 în 6) |
| 5 | 6 | 1 |
| 5 | 3 | 2 (am schimbat poţiunea din 6 în 3) |
| 6 | 3 | 2 |
| 5 | 3 | 2 (observaţi cum aici am mers la stânga, lucru care este permis deoarece am vizitat deja aceasta pozitie) |
| 4 | 3 | 2 |
| 3 | 3 | 2 |
| 3 | 1 | 3 (am schimbat poţiunea din 3 în 1) |
| 2 | 1 | 3 |
| 2 | 2 | 4 (am schimbat poţiunea din 1 în 2) |
| 1 | 2 | 4 |
| 2 | 2 | 4 |
| 3 | 2 | 4 |
| 4 | 2 | 4 |
| 5 | 2 | 4 |
| 6 | 2 | 4 |
| 7 | 2 | 4 |
| 7 | 1 | 5 (am schimbat poţiunea din 2 în 1) |
| 8 | 1 | 5 |
 

🤡🤡🤡

== include(page="template/taskfooter" task_id="expanding") ==