Дан массив \(a = [1, 2, \ldots, n]\), где \(n\) — нечетное, и целое число \(k\).
Ваша задача — выбрать нечетное положительное целое число \(m\) и разбить массив \(a\) на \(m\) подмассивов\(^{\dagger}\) \(b_1, b_2, \ldots, b_m\) так, чтобы:
- Каждый элемент массива \(a\) принадлежит ровно одному подмассиву.
- Для всех \(1 \le i \le m\), \(|b_i|\) — нечетное, т.е. длина каждого подмассива нечетная.
- \(\operatorname{median}([\operatorname{median}(b_1), \operatorname{median}(b_2), \ldots, \operatorname{median}(b_m)]) = k\), т.е. медиана\(^{\ddagger}\) массива медиан всех подмассивов должна равняться \(k\). \(\operatorname{median}(c)\) обозначает медиану массива \(c\).
\(^{\dagger}\)Подмассив массива \(a\) длины \(n\) — это массив \([a_l, a_{l + 1}, \ldots, a_r]\) для некоторых целых чисел \(1 \le l \le r \le n\).
\(^{\ddagger}\)Медиана массива нечетной длины — это средний элемент после сортировки массива в неубывающем порядке. Например: \(\operatorname{median}([1,2,5,4,3]) = 3\), \(\operatorname{median}([3,2,1]) = 2\), \(\operatorname{median}([2,1,2,1,2,2,2]) = 2\).
Выходные данные
Для каждого набора входных данных:
- Если подходящего разбиения нет, выведите \(-1\) в одной строке.
- В противном случае, в первой строке выведите нечетное целое число \(m\) (\(1 \le m \le n\)) — количество подмассивов в разбиении, а во второй строке выведите \(m\) различных целых чисел \(p_1, p_2 , p_3 , \ldots, p_m\) (\(1 = p_1 < p_2 < p_3 < \ldots < p_m \le n\)) — обозначающие левые границы каждого подмассива.
А именно, для корректного ответа \([p_1, p_2, \ldots, p_m]\):
- \(b_1 = \left[ a_{p_1}, a_{p_1 + 1}, \ldots, a_{p_2 - 1} \right]\)
- \(b_2 = \left[ a_{p_2}, a_{p_2 + 1}, \ldots, a_{p_3 - 1} \right]\)
- \(\ldots\)
- \(b_m = \left[ a_{p_m}, a_{p_m + 1}, \ldots, a_n \right]\).
Если существует несколько решений, вы можете вывести любое из них.
Примечание
В первом наборе входных данных при данном разбиении \(m = 1\) и \(b_1 = [1]\). Очевидно, что \(\operatorname{median}([\operatorname{median}([1])]) = \operatorname{median}([1]) = 1\).
Во втором наборе входных данных при данном разбиении \(m = 3\) и:
- \(b_1 = [1]\)
- \(b_2 = [2]\)
- \(b_3 = [3]\)
Следовательно, \(\operatorname{median}([\operatorname{median}([1]), \operatorname{median}([2]), \operatorname{median}([3])]) = \operatorname{median}([1, 2, 3]) = 2\).
В третьем наборе входных данных нет корректного разбиения для \(k = 3\).
В четвертом наборе входных данных при данном разбиении \(m = 5\) и:
- \(b_1 = [1, 2, 3]\)
- \(b_2 = [4, 5, 6]\)
- \(b_3 = [7, 8, 9]\)
- \(b_4 = [10, 11, 12]\)
- \(b_5 = [13, 14, 15]\)
Следовательно, \(\operatorname{median}([\operatorname{median}([1, 2, 3]), \operatorname{median}([4, 5, 6]), \operatorname{median}([7, 8, 9]), \operatorname{median}([10, 11, 12]), \operatorname{median}([13, 14, 15])]) = \operatorname{median}([2, 5, 8, 11, 14]) = 8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1
3 2
3 3
15 8
|
1
1
3
1 2 3
-1
5
1 4 7 10 13
|