!>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:
📖 Povestea reformulată în română
* Ei pornesc la o poziţie $p$, cu o poţiune de putere $c = a{~p~}$.
Î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.
* 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.
ake, fiind elastic, poate alege o poziţie iniţială p din şir, şi începe o călătorie de extindere:
* O mutare într-o poziţie vizitată anterior este mereu posibilă şi nu are niciun efect.
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.
* Pentru a vizita o poziţie nevizitată, trebuie să aibă puterea poţiunii $c$ egală cu valoarea poziţiei în care merg.
Reguli magice:
* Pentru un ban, ei pot schimba puterea poţiunii $c$ la orice valoare pozitivă.
Jake poate schimba energia c în orice valoare pozitivă, dar asta costă 1 poţiune magică.
* Când ajung într-o poziţie nouă, ei colectează piatra din acea poziţie.
Dacă în stânga există o piatră cu energia c, atunci Jake poate sări la ea şi l scade 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~}$.
Dacă în dreapta există o piatră cu energia c, atunci Jake se întinde până la ea şi r creşte cu 1.
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)$.
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?
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
