Zadanie

Excelentný Excel

Počet bodov: 30, časový limit: 2000ms

Šéf Korporácie Siahodlhých Písomností sa pozerá na siahodlhý hárok v Exceli. Chce v ňom nájsť veľa dôležitých údajov, ale hárok je veľmi dlhý a skrolovanie v ňom zaberá veľmi veľa času. Šéf presne vie, na ktoré riadky sa chce pozrieť a dokonca aj to, v akom poradí. Len keby to netrvalo tak dlho.

Šéfov hárok má \(n\) riadkov očislovaných od \(1\) po \(n\). Na obrazovku jeho počítača sa vojde vždy \(k\) po sebe idúcich riadkov. Na začiatku sú na obrazovke zobrazené riadky \(1\) až \(k\). Šéf sa chce pozrieť na \(m\) riadkov v danom poradí, tieto riadky nemusia byť rôzne.

Ak sú na obrazovke riadky \(i\) až \(i+k-1\) a chceme si zobraziť riadky \(j\) až \(j+k-1\), kde \(i \neq j\), potrebujeme použiť jedno skrolovanie dĺžky \(\left|i-j\right|\).

Nájdite najkratšiu postupnosť skrolovaní, ktorú šéf KSP musí použiť, aby si prečítal všetky žiadané riadky. Najkratšia postupnosť skrolovaní je taká, ktorá obsahuje najmenej skrolovaní a spomedzi všetkých takých je súčet dĺžok jednotlivých skrolovaní najmenší možný.

Vstup a výstup

Na prvom riadku dostanete tri celé čísla \(n,\ k,\ m\) – počet všetkých riadkov v hárku, počet riadkov, ktoré sa dajú vidieť naraz a počet riadkov, na ktoré sa chce šéf pozrieť. Platí \(1 \leq k \leq n \leq 10^9\) a \(1 \leq m \leq 500000\).

Nasleduje \(m\) riadkov, \(i\)-ty z nich obsahuje číslo \(1 \leq r_i \leq n\) – číslo riadku, ktorý chce šéf vidieť ako \(i\)-ty v poradí.

Vypíšte dve čísla oddelené medzerou – minimálny počet potrebných skrolovaní a najmenšiu možnú preskrolovanú vzdialenosť (súčet dĺžok jednotlivých skrolovaní). Výstup nezabudnite ukončiť znakom nového riadka.

Príklady

Input:

20 10 2
10
20

Output:

1 10

Najskôr si šéf prečíta riadok \(10\), potom preskroluje na riadky \(11\) až \(20\) a prečíta si tie.

Input:

20 10 2
10
7

Output:

0 0

Žiadne skrolovanie nie je potrebné.

Input:

20 8 3
1
11
4

Output:

1 3

Po prečítaní prvého riadku stačí preskrolovať na riadky \(4\) až \(11\).