vaporeon

Blanche, liderul echipei Mystic, a fost capturată de echipa Lacheta! Ea a fost adusă într-o bază a echipei care conține $N$ obstacole numerotate de la $1$ la $N$, fiecare obstacol $i$ având rezistența $R[i]$. Inițial, Blanche este plasată în dreptul celui de-al $x$-lea obstacol. Încercând să scape, ea îl eliberează pe Vaporeon care distruge al $x$-lea obstacol și capătă puterea de atac $A$ egală cu $R[x]$.

Pentru a evada, Vaporeon trebuie să distrugă toate obstacolele rămase. La un moment de timp la care Vaporeon a distrus toate obstacolele din intervalul $[x, y]$, el poate executa exact una din mișcările:

1. Hydro Pump pe obstacolul $x-1$ , dacă $x-1 ≥ 1$ și $R[x-1] ≤ A$.
2. Hydro Pump pe obstacolul $y+1$ , dacă $y+1 ≤ N$ și $R[y+1] ≤ A$.
3. Work Up, care crește puterea de atac $A$ la valoarea minimă dintre $R[x-1]$ și $R[y+1]$.
   Dacă doar unul din obstacole există, puterea de atac crește la valoarea rezistenței acestuia.

O mișcare Hydro Pump necesită efort $1$, în timp ce o mișcare Work Up necesită efort $K$. Notăm cu $E[x]$ efortul necesar evadării pornind din al $x$-lea obstacol. $E[x]$ este egal cu suma minimă a eforturilor necesare pentru a distruge cele $N$ obstacole, dacă Vaporeon a început din al $x$-lea obstacol.

Echipa Lacheta a anticipat această strategie, așa că studiază diferite aranjamente ale obstacolelor, cât și diferite poziții în care să o plaseze inițial pe Blanche. Ei vă vor da numărul de obstacole $N$, efortul $K$ necesar unei mișcări și rezistențele celor $N$ obstacole. Apoi, ei vă vor cere să efectuați următoarele operații:

1. Să schimbați două obstacole adiacente $x$ și $x + 1$ .
2. Să spuneți, pentru doi indici $x$ și $y$, care este suma $E[x] + E[x+1] + ... + E[y]$ pentru aranjamentul actual al obstacolelor.

Implementare

Programul vostru va trebui să implementeze următoarele funcții:

int initialize(int N, int K, int* R);

Această funcție este apelată o singură dată la începutul executării programului. Parametrii $N$, respectiv $K$ reprezintă numărul de obstacole, respectiv efortul necesar pentru o mișcare Work Up. Parametrul $R$ este un array de lungime $N$, indexat de la 0 , elementul de pe poziția $i$ al acestuia reprezentând rezistența obstacolului $i + 1$.

void exchange(int x);

Această funcție este apelată pentru fiecare interschimbare de obstacole efectuată. Parametrul $x$ reprezintă faptul că se interschimbă obstacolele de pe pozițiile $x$ și $x + 1$.

long long query(int x, int y);

Această funcție este apelată de mai multe ori, o dată pentru fiecare întrebare a echipei Lacheta. Primind parametrii $x$ și $y$, trebuie să returnați suma $E[x] + E[x+1] + ... + E[y]$ pentru aranjamentul actual al obstacolelor.

Pe lângă funcțiile pe care le veți implementa, puteți declara variabile locale sau globale și puteți implementa alte funcții ajutătoare. Se recomandă ca variabilele globale și funcțiile să fie declarate cu modificatorul static.

Testare

Pentru a vă testa local soluțiile, vă oferim programul main.cpp și header-ul vaporeon.h . Programul main.cpp citește din fișierul de intrare vaporeon.in, apelează funcțiile initialize, exchange și query ale concurentului și afișează răspunsul returnat de fiecare apel la funcția query.

Pe prima linie a fișierului vaporeon.in se află numerele naturale $N$ și $K$. Pe a doua linie se află $N$ numere naturale, reprezentând elementele array-ului $R$. Pe următoarele linii se află descrise operațiile:

• 1 x, dacă avem un apel exchange(x)
• 2 x y, dacă avem un apel query(x, y)

Pe fiecare linie a fișierului vaporeon.out se află, în ordine, răspunsurile returnate de funcția query.

Restricții și precizări

• $1 ≤ N ≤ 100 \ 000$
• $1 ≤ K ≤ 1 \ 000 \ 000$
• $1 ≤ R[i] ≤ 1 \ 000 \ 000 \ 000$
• Numărul total de apeluri la funcțiile exchange și query nu depășește $200 \ 000$.
• Pentru 20% din teste, $N ≤ 1 \ 000$ și numărul total de apeluri la funcțiile exchange și query nu depășește $2 \ 000$.

Exemplu

vaporeon.in

5 3 
2 3 1 4 1
2 2 2
2 1 5
1 2
2 2 2
2 1 5

vaporeon.out

7
38
13
41

Explicație

Apelurile efectuate sunt:
initialize(5, 3, {2,3,1,4,1})
query(2, 2) - returnează $7$
query(1, 5) - returnează $38$
exchange(2)
query(2, 2) - returnează $13$
query(1, 5) - returnează $41$

Pentru primul query, Vaporeon pleacă din obstacolul de pe poziția $2$ cu puterea $3$. El execută:
Hydro Pump $1$
Hydro Pump $3$
Work Up (capătă puterea $4$)
Hydro Pump $4$
Hydro Pump $5$

După operația de exchange, obstacolele au configurația $\{2, 1, 3, 4, 1\}$

Pentru al treilea query, Vaporeon pleacă din obstacolul de pe poziția $2$ cu puterea $1$. El execută:
Work Up (capătă puterea $2$) .
Hydro Pump $1$
Work Up (capătă puterea $3$)
Hydro Pump $3$
Work Up (capătă puterea $4$)
Hydro Pump $4$
Hydro Pump $5$