E. Райский Тур
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

История не была закончена, как думал PMP. Бог предложил ему еще один шанс перевоплотиться и вернуться к жизни. Но прежде чем он сможет вернуться, Бог сказал ему, что PMP должен расспросить n великих людей, включая выдающихся программистов, об их жизненном опыте.

Эти люди стоят на одной прямой. Они пронумерованы от 1 до n слева направо. Человек номер i стоит в точке с координатой xi (xi < xi + 1, i < n). PMP должен посетить всех этих людей одного за другим в произвольном порядке. Каждого человека надо посетить ровно один раз. PMP начинает обход, подойдя к месту s-го человека, после чего вступает с ним в разговор и перенимает его опыт.

Каждый раз, когда PMP хочет изменить свою позицию, он должен дать билет ангелу, и ангел относит его к месту назначения. Ангелы берут PMP в одном месте, летят к пункту назначения и приземляют его там. При перемещении они никого не посещают. Перелет от i-го до j-го человека занимает |xi - xj| времени. PMP может вернуться к жизни, как только он посетит всех людей.

Есть два вида ангелов: некоторые ангелы летают вправо и принимают только билеты направо. Другие летят налево и принимают только билеты налево. Есть неограниченное количество ангелов каждого типа. PMP имеет l левых билетов и n - 1 - l правых билетов.

PMP хочет вернуться к жизни как можно скорее, чтобы не упустить возможность поучаствовать в финале этого года вместо прошлогоднего финала, который он пропустил. Он хочет узнать самый быстрый способ посетить всех людей ровно по одному разу. Он также должен знать точную последовательность передвижений, которые он должен выполнить.

Входные данные

Первая строка входного файла содержит через пробел три целых числа n, l, s (2 ≤ n ≤ 105, 0 ≤ l < n, 1 ≤ s ≤ n) — количество людей, которых надо посетить, количество билетов налево в распоряжении PMP и его изначальное положение. Следующая строка содержит n целых чисел через пробел. На этой строке i-ое целое число — xi (0 = x1 < x2 < ... < xn ≤ 109) — позиция i-го человека.

Выходные данные

Если PMP не сможет посетить всех людей с билетами, которые у него есть, выведите -1 в единственной строке выходного файла. В противном случае, выведите на первой строке минимальное количество времени, за которое PMP может посетить всех людей. На второй строке выведите n - 1 целых чисел — номера людей, которых должен посетить PMP в порядке, формирующем оптимальное решение. Если ответов несколько, выведите любой.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.

Примеры
Входные данные
5 2 2
0 10 11 21 22
Выходные данные
33
1 3 5 4
Входные данные
4 3 1
0 1 2 3
Выходные данные
-1
Входные данные
7 3 2
0 100 200 201 301 303 305
Выходные данные
409
1 3 4 7 6 5
Примечание

Помянем величайшего программиста всех времен, который покинул нас около года назад. Покойся с миром, Ренат Муллаханов.