== include(page="template/taskheader" task_id="voodoo") ==
Se dă [$N$], [$X$], $Y$ și un șir de $N$ numere naturale $a[~1~]$, $a[~2~]$, ..., $a[~N~]$.
Definim costul unui rearajament $p$ al șirului $a$ ca fiind suma tuturor subsecvențelor $(i, j)$ astfel încât $1$ ≤ $i$ ≤ $X$ și $Y$ ≤ $j$ ≤ [$N$]. Costul poate fi calculat astfel:
Se dă $*N*$, $*X*$, $*Y*$ și un șir de $*N*$ numere naturale $*a*[~1~]$, $*a*[~2~]$, ..., $*a*~*N*~$.
Definim costul unui rearajament $*p*$ al șirului $*a*$ ca fiind suma tuturor subsecvențelor $(i, j)$ astfel încat $1$ ≤ $i$ ≤ $*X*$ și $*Y*$ ≤ $j$ ≤ $*N*$. Costul poate fi calculat astfel:
!problema/voodoo?pseudocod2!
Aflați costul minim al unei rearanjări a șirului $a$ cât și o rearanjare ce obține acest cost minim.
Aflați costul minim al unei rearanjări a șirului $*a*$ cât și o rearanjare ce obține acest cost minim.
h2. Date de intrare
Fișierul de intrare voodoo.in conține pe prima linie, în această ordine numerele naturale [$N$], [$X$], [$Y$], separate prin câte un spațiu. Pe cea de-a doua linie se află $N$ numere naturale separate prin câte un spațiu, reprezentând șirul [$a$].
Fișierul de intrare $voodoo.in$ conține pe prima linie, în aceast ordine numerele naturale $*N*$, $*X*$, $*Y*$, separate prin spațiu. Pe cea de-a doua linie se află $*N*$ numere naturale separate prin spațiu, reprezentând șirul $*a*$.
h2. Date de ieșire
Pe prima linie a fișierul de ieșire voodoo.out se află costul minim al unei rearanjări a șirului [$a$], iar pe a doua linie se află $N$ numere naturale separate prin câte un spațiu care reprezintă o rearanjare a șirului $a$ ce obține cost minim.
Pe prima linie a fișierul de ieșire $voodoo.out$ se află costul minim al unei rearanjări a șirului $*a*$, iar pe a doua linie se afla $*N*$ numere naturale care reprezintă o rearanjare a șirului $*a*$ ce obține cost minim.
h2. Restricții
* $1$ ≤ $X$ < $Y$ ≤ $N$ ≤ $1.000.000$
* $0$ ≤ $a[~i~]$ ≤ $1.000.000$, pentru fiecare $i$ de la $1$ la $N$
* se garantează că răspunsul se incadrează pe tipul de date $long long$
* printr-un rearanjament al unui șir întelegem o reordonare a termenilor acestuia
* se acordă $50%$ din punctaj pentru afișarea costului minim corect
* pentru $30%$ din punctaj, se garantează că $N$ ≤ $1.000$
* pentru $60%$ din punctaj, se garantează că $N$ ≤ $10.000$
* *ATENȚIE!* Din cauza dimensiunii mari a datelor de intrare si de ieșire, se recomandă parsarea intrării și a ieșirii. Vă oferim o implementare suficientă pentru rezolvarea acestei probleme "aici":TODO.
* $1$ ≤ $*X*$ < $*Y*$ ≤ $*N*$ ≤ $1.000.000$
* $0$ ≤ $*a*~*i*~$ ≤ $1.000.000$, pentru fiecare $i$ de la $1$ la $*N*$
* Se garantează că răspunsul se incadreaza pe tipul de date $long long$
* $50%$ din punctaj se acordă pentru afișarea costului minim corect
* $30%$ din teste satisfac $*N*$ ≤ $1.000$
* $60%$ din teste satisfac $*N*$ ≤ $10.000$
h2. Exemplu
h3. Explicație
Pentru primul exemplu, o rearanjare de cost minim este $2 1 3 4 5$, costul acestei rearanjari este:
Pentru primul exemplu, rearanjarea este $2 1 3 4 5$, costul acestei rearanjari este:
$(2 + 1) + (2 + 1 + 3) + (2 + 1 + 3 + 4) + (2 + 1 + 3 + 4 + 5) =$
$3 + 6 + 10 + 15 = 34$
Nu există nicio altă rearanjare cu cost mai mic.
Se poate demonstra ca nu exista alta rearanjare cu costul mai mic.
Pentru al doilea exemplu, rearanjarea este $5 3 1 3 4$, costul acestei rearanjari este:
$(5 + 3 + 1 + 3) + (5 + 3 + 1 + 3 + 4) + (3 + 1 + 3) + (3 + 1 + 3 + 4) =$
