Kuten tehtävässä A, sinun tulee etsiä pienin kokonaiskustannus hauille. Kuitenkin saat järjestää listan kahdesti: ensin ennen hakuja ja sitten jossain vaiheessa myöhemmin kahden haun välissä. Haut suoritetaan siinä järjestyksessä kuin ne on annettu.

Tehtäväsi on ilmoittaa pienin hakujen kokonaiskustannus vasemmalta oikealle jokaiselle muutoskohdalle, jossa voit järjestää listan uudestaan.

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 m-1 lukua: pienin kokonaiskustannus jokaiselle muutoskohdalle.

Esimerkki

Syöte:

4 8
1 2 1 1 4 4 2 1

Tuloste:

14 13 13 12 14 13 14

Selitys: Esimerkiksi kokonaiskustannus 12 voidaan saada seuraavasti:

• Valitaan ensin listan järjestys [1,2,4,3].
• Suoritetaan haut [1,2,1,1] (kustannus 1+2+1+1=5).
• Valitaan uusi listan järjestys [4,1,2,3].
• Suoritetaan haut [4,4,2,1] (kustannus 1+1+3+2=7).

Osatehtävä 1 (20 pistettä)

• 1 \le n \le 100
• 1 \le m \le 1000

Osatehtävä 2 (30 pistettä)

• 1 \le n \le 10^5
• 1 \le m \le 1000

Osatehtävä 3 (50 pistettä)

• 1 \le n \le 10^5
• 1 \le m \le 10^5