moara

Una-i să sortezi cartoane, alta-i să sortezi vagoane!

La poarta unei mori se află $n$ saci, etichetaţi cu numere de la $1$ la $n$, aşezaţi în linie, într-o ordine dată. Sacul cu eticheta $i$ are greutatea $g_i$.

Morarul cere ucenicului său să reaşeze sacii în ordinea crescătoare a etichetelor. Cum nu este spaţiu de manevră pentru a schimba sacii între ei, ucenicul ia un scaun şi-l aşează lângă poziţia $k$ din şir, alege un sac şi-l pune pe scaun, ia alt sac şi-l mută în locul gol, apoi aduce alt sac în locul eliberat de acesta, etc., sau aduce sacul de pe scaun în locul rămas gol. Repetă procedeul până când sacii ajung în ordinea cerută de morar. Scaunul nu se mută. Efortul depus de ucenic pentru mutatul unui sac, indiferent dacă acesta a fost pus sau nu pe scaun, este egal cu produsul dintre greutatea sacului şi distanţa pe care a fost transportat sacul. Distanţa dintre doi saci alăturaţi este egală cu unitatea.

Cerință

Se cere să se stabilească poziţia amplasării scaunului şi ordinea schimbării sacilor între ei, astfel încât ucenicul să facă un număr minim de mutări şi efortul depus de acesta să fie minim pentru numărul de mutări.

Date de intrare

Fişierul de intrare moara.in conţine pe prima linie numărul de saci $n$, pe a doua linie ordinea aşezării sacilor, iar pe a treia linie şirul greutăţilor sacilor $g_1, g_2, \dots, g_n$.

Date de ieșire

Ieşirea se va face în fişierul moara.out, care va conţine:

• pe prima linie p k e, unde $p$ este poziţia scaunului, $k$ este numărul de mutări şi $e$ este valoarea efortului depus;
• pe fiecare din liniile următoare câte o mutare de forma d s, unde $d$ este poziţia destinaţie şi $s$ este poziţia sursă, poziţia scaunului se va nota cu $0$.

Restricții și precizări

• $2 \le n \le 5\ 000$
• $1 \le k \le n$
• $1 \le g_i < 256$, pentru $1 \le i \le n$
• Se acordă $30\%$ din punctaj dacă numărul de mutări afișat este corect și încă $30\%$ dacă efortul afișat este corect.

Exemplu

moara.in

5
2 4 3 5 1
3 5 1 2 4

moara.out

3 5 25
0 2
2 1
1 5
5 4
4 0