В Центральной Компании есть офис со сложной системой безопасности. В офисе работает \(10^6\) сотрудников, пронумерованных от \(1\) до \(10^6\).
Система безопасности записывает в лог входы и выходы из офиса. Вход \(i\)-го работника описывается числом \(i\), а выход \(i\)-го работника описывается числом \(-i\).
У компании есть строгие правила:
- Сотрудник может зайти в офис не более одного раза за день.
- Очевидно, сотрудник не может выйти из офиса если он не зашел в него ранее в этот день.
- В начале и конце каждого дня офис пуст (сотрудники не могут оставаться в офисе на ночь). Он также может быть пуст в любой момент дня.
Любой массив событий, удовлетворяющий этим правилам называется корректным днем.
Приведем некоторые примеры корректных или некорректных дней:
- \([1, 7, -7, 3, -1, -3]\) это корректный день (\(1\) входит, \(7\) входит, \(7\) выходит, \(3\) входит, \(1\) выходит, \(3\) выходит).
- \([2, -2, 3, -3]\) это также корректный день.
- \([2, 5, -5, 5, -5, -2]\) это некорректный день, потому что \(5\) зашел в офис дважды в течение одного дня.
- \([-4, 4]\) это некорректный день, потому что \(4\) вышел из офиса, не заходя в него.
- \([4]\) это некорректный день, потому что \(4\) вошел в офис и не вышел из него до конца дня.
Есть \(n\) событий \(a_1, a_2, \ldots, a_n\), в порядке, в котором они происходили. Этот массив соответствует одному или нескольким последовательным дням. Системный администратор по ошибке удалил номера дней, но он не менял порядок событий.
Ваша задача разбить (разрезать) массив событий \(a\) на последовательные подотрезки, которые должны образовывать непустые корректные дни (или определить, что это невозможно). Каждый элемент массива должен принадлежать ровно одному подотрезку разбиения. Каждый последовательный подотрезок массива должен образовывать корректный день.
К примеру, если \(n=8\) и \(a=[1, -1, 1, 2, -1, -2, 3, -3]\), тогда его можно разбить на два последовательных подотрезка, каждый из которых является корректным днем: \(a = [1, -1~ \boldsymbol{|}~ 1, 2, -1, -2, 3, -3]\).
Помогите администратору корректно разбить \(a\) или определите, что это невозможно. Найдите любое подходящее разбиение, вам не нужно минимизировать или максимизировать количество частей.
Выходные данные
Если не существует корректного разбиения, выведите \(-1\). Иначе, выведите любое корректое разбиение в следующем формате:
- В первой строке выведите количество дней \(d\) (\(1 \le d \le n\)).
- Во второй строке, выведите \(d\) целых чисел \(c_1, c_2, \ldots, c_d\) (\(1 \le c_i \le n\) and \(c_1 + c_2 + \ldots + c_d = n\)), где \(c_i\) это количество событий в \(i\)-м дне.
Если есть несколько возможных решений, вы можете вывести любое из них. Вам необязательно минимизировать или максимизировать количество дней.
Примечание
В первом примере весь массив является корректным днем.
Во втором примере, один из возможных способов это разбить массив на \([1, -1]\) и \([1, 2, -1, -2, 3, -3]\) (\(d = 2\) и \(c = [2, 6]\)). Единственное другое возможное решение это разбить на \([1, -1]\), \([1, 2, -1, -2]\) и \([3, -3]\) (\(d = 3\) и \(c = [2, 4, 2]\)). Оба решения принимаются.
В третьем и четвертом примерах, можно доказать, что решения нет. Пожалуйста, обратите внимание, что массив данный во вводе не является гарантированно корректным набором событий.