!>problema/expanding?poza_expand2.png!
📖 Povestea reformulată în română
Î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 (o culoare sau o energie), iar fiecare valoare apare de cel mult două ori în tot şirul.
* Ei pornesc la o poziţie $p$, cu o poţiune de putere $c = a{~p~}$.
ake, fiind elastic, poate alege o poziţie iniţială p din şir, şi începe o călătorie de extindere:
* 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.
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.
* O mutare într-o poziţie vizitată anterior este mereu posibilă şi nu are niciun efect.
Reguli magice:
* Pentru a vizita o poziţie nevizitată, trebuie să aibă puterea poţiunii $c$ egală cu valoarea poziţiei în care merg.
Jake poate schimba energia c în orice valoare pozitivă, dar asta costă 1 poţiune magică.
* Pentru un ban, ei pot schimba puterea poţiunii $c$ la orice valoare pozitivă.
Dacă în stânga există o piatră cu energia c, atunci Jake poate sări la ea şi l scade cu 1.
* Când ajung într-o poziţie nouă, ei colectează piatra din acea poziţie.
Dacă în dreapta există o piatră cu energia c, atunci Jake se întinde până la ea şi r creşte cu 1.
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~}$.
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.
Pentru fiecare dintre ele, trebuie să spui câte poţiuni magice minime are nevoie Jake ca să se întindă pe tot şirul.
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?
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)$.
h2. Date de intrare
* $1 ≤ p ≤ n$
|_. # |_. Punctaj |_. Restricţii |
| 1 | 10 | $n ≤ 500$ şi $q ≤ 500$ |
| 2 | 10 | $n ≤ 5000$ şi $q ≤ 10$ |
| 1 | 8 | $n ≤ 500$ şi $q ≤ 500$ |
| 2 | 9 | $n ≤ 5000$ şi $q ≤ 10$ |
| 3 | 15 | $n ≤ 5000$ şi $q ≤ 5000$ |
| 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$ |
| 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$ |
h2. Exemplu
table(example). |_. sandwich.in |_. sandwich.out |
table(example). |_. expanding.in |_. expanding.out |
| 8
2 1 3 4 6 3 2 1
8
