Lista sisältää kokonaisluvut 1,2,\dots,n, ja siihen suoritetaan m hakua, jossa haetaan tietty luku listalta. Kussakin haussa listaa käydään läpi vasemmalta oikealle, kunnes haettava luku löytyy.

Haun kustannus on yhtä suuri kuin niiden lukujen määrä, jotka käydään läpi haun aikana. Esimerkiksi kun lista on [1,2,4,3] ja haettava luku on 4, haun kustannus on 3, koska haussa käydään läpi luvut 1, 2 ja 4.

Tehtäväsi on valita listan luvuille järjestys, jossa hakujen kokonaiskustannus eli kustannusten summa on mahdollisimman pieni.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua n ja m: listan koko ja hakujen määrä.

Toisella rivillä on m lukua: haettavat luvut. Jokainen haettava luku on listalla.

Tuloste

Tulosta ensimmäiselle riville pienin mahdollinen hakujen kokonaiskustannus.

Tulosta toiselle riville esimerkki tavasta järjestää lista niin, että tämä kokonaiskustannus toteutuu. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Esimerkki

Syöte:

4 8
1 2 1 1 4 4 2 1

Tuloste:

14
1 2 4 3

Selitys: Kun listan järjestys on [1,2,4,3], kustannukset ovat seuraavat:

• Luvun 1 hauista tulee kustannus 4 \cdot 1 = 4.
• Luvun 2 hauista tulee kustannus 2 \cdot 2 = 4.
• Luvun 3 hauista tulee kustannus 0 \cdot 4 = 0.
• Luvun 4 hauista tulee kustannus 2 \cdot 3 = 6.

Tästä saadaan kokonaiskustannus 4+4+0+6=14, joka on pienin mahdollinen.

Arvostelu

Jokaisessa testissä 1 \le n \le 100 ja 1 \le m \le 1000. Saat tehtävästä 100 pistettä, jos koodisi tuottaa oikean tuloksen kaikissa testeissä.