D. Важные функции

Задачу добавил: alef

Успешно сдано решений: 16

Ограничение по времени: 2 с

Ограничение по памяти: 256 Мб

Министр безопасности Пафнутий предложение высказал: нужен человек, который будет заранее в залу приходить и измерять температуру. Ежели слишком жарко или слишком холодно окажется — будет время, чтобы протопить залу или же проветрить. На что министр экономики Калистрат возразил, что пора уже переходить к современным технологиям: надобно, чтобы котельная автоматически меняла режим отопления в зависимости от прогноза погоды. Да и пора уже спроектировать систему «Умный Дворец». Что министр науки на это скажет?

Министр науки Фалалей сообщил, что разработка такой системы уже ведётся, однако ввиду того, что система большая и сложная, внедрять её придётся по частям. Базовая часть уже почти готова, осталось лишь уточнить, какие функции она будет реализовывать. Поэтому Фалалей предлагает каждому министру указать наиболее важную функцию, которую этот министр считает необходимой в базовой части системы.

Чтобы проект по внедрению базовой части был утверждён, его должны поддержать не менее $m$ из $n$ министров. Министр поддержит проект, если в нём будет реализована указанная им функция.

Ради простоты обозначим функции системы целыми числами. Чем меньше по абсолютной величине отличаются друг от друга эти числа, тем более близкими будут соответствующие им функции, и тем проще эти функции реализовывать совместно.

Назовем сложностью проекта максимальную (по абсолютной величине) разность между входящими в него функциями. Министр науки Фалалей, разумеется, хочет, чтобы проект был поддержан. Но вместе с тем он хочет, чтобы этот проект имел минимально возможную сложность. Ваша задача — определить, какие функции следует включить в проект, чтобы пожелания Фалалея были выполнены.

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

В первой строке содержатся целые числа $n$ и $m$ $(1 \leq m \leq n \leq 3 \cdot 10^{5})$ — общее количество министров и количество министров, необходимое для утверждения проекта.

Во второй строке содержится $n$ целых чисел $f_{1}, f_{2}, \dots, f_{n}$ $(1 \leq f_{j} \leq 10^{6}, j = 1, 2, \dots, n)$ , $f_{j}$ — числовое обозначение функции, указанной министром $# j$ .

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

В первой строке выведите минимально возможную сложность проекта и количество министров, фактически поддержавших проект.

Во второй строке выведите номера министров, поддержавших проект, в порядке возрастания.

Если существует несколько вариантов ответа, выведите вариант, который поддержит максимальное количество министров. Если и в этом случае вариантов ответа несколько, выведите любой из них.

Примеры

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

11 5
18 9 1 11 18 4 9 18 16 4 11

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

7 6 
2 4 6 7 10 11

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

14 7
15 21 13 7 10 5 19 20 13 21 3 5 12 13

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

8 8 
3 4 5 6 9 12 13 14

Примечание

Поясним приведённые примеры.

В первом примере необходимо, чтобы проект поддержали хотя бы $5$ министров.

Как можно видеть, в предложенном ответе два министра ( $# 2$ и $# 7$ ) хотят видеть в базовой части системы функцию $9$ , ещё два министра ( $# 6$ и $# 10$ ) считают необходимой реализацию функции $4$ , и, наконец, ещё двум министрам ( $# 4$ и $# 11$ ) представляется необходимой функция $11$ . Таким образом, фактическое количество министров, готовых поддержать проект, окажется равным $6$ , в нём будет реализовано $3$ функции, а сложность этого проекта составит $7$ .

Можно заметить, что это не единственно возможный ответ, существует ещё два допустимых варианта.

Если в предыдущем проекте функцию $4$ заменить на функцию $16$ , можно будет получить поддержку $5$ министров: хотя министры $# 2$ и $# 7$ не будут поддерживать проект, его одобрит министр $# 9$ . Сложность этого проекта также будет $7$ , функций в нём будет реализовано $3$ , поэтому он ничуть не хуже предшествующего.

Также сложность $7$ имеет проект, в котором реализованы другие три функции — функция $11$ , функция $16$ и функция $18$ . Такой проект, как и первый, поддержат шесть министров: министры $# 4$ и $# 11$ желают видеть функцию $11$ , министр $# 9$ будет доволен наличием функции $16$ , а министры $# 1$ , $# 5$ и $# 8$ одобряют функцию $18$ .

Другие проекты, которые могут быть поддержаны пятью и более министрами, имеют большую сложность, и тем самым проигрывают вышеперечисленным.

Сдать задачу

Задать вопрос жюри по этой задаче

Login:
Password:
	Забыли пароль?