Мама хочет подарить маленькой девочке Алёне массив из n целых неотрицательных чисел. Но массив должен быть особенным.
Алёна девочка капризная, поэтому когда мама подарит ей массив, Алёна рассмотрит m подмассивов подаренного ей массива. Назовем подмассивом некоторую последовательность из подряд идущих чисел в массиве. i-й подмассив задается двумя числами li и ri, и он состоит из чисел a[li], a[li + 1], ..., a[ri].
Капризная Алёна посмотрит на mex каждого подмассива. Среди всех m mex-ов девочка выберет минимальный, и она хотела бы, чтобы минимальный mex был как можно больше.
Ваша задача найти массив a из n неотрицательных чисел такой, чтобы минимальный mex подмассивов, заданных Алёной, был максимален.
mex множества чисел S — это минимальное неотрицательное целое число, которое не встречается в множестве S.
Выходные данные
В первой строке выведете одно число — максимально возможный минимальный mex.
Во второй строке выведете n чисел — массив a. Числа в массиве a должны быть от 0 до 109.
Гарантируется, что существует оптимальный ответ, в котором все числа в массиве a находятся в пределах от 0 до 109.
Если существует несколько решений, выведите любое.
Примечание
Пояснение к тесту из условия: на подмассиве (1, 3) mex равен 3, на подмассиве (2, 5) mex равен 3 и на подмассиве (4, 5) mex тоже равен 2, следовательно минимальный mex среди подмассивов, интересующих Алёну, равен 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
1 3
2 5
4 5
|
2
1 0 2 1 0
|
|
2
|
4 2
1 4
2 4
|
3
5 2 0 1
|