Это простая версия задачи. Разница между версиями заключается в том, что в этой версии массив не содержит нулей. Вы можете делать взломы только в том случае, если обе версии задачи решены.
Вам дан массив \([a_1, a_2, \ldots a_n]\), состоящий из чисел \(-1\) и \(1\). Требуется предъявить разбиение этого массива на несколько отрезков \([l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]\), обладающее следующим свойством:
- Обозначим за \(s_i\) знакопеременную сумму элементов в \(i\)-м отрезке, то есть \(s_i\) = \(a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + \ldots \pm a_{r_i}\). Например знакопеременная сумма на отрезке \([2, 4]\) в массиве \([1, 0, -1, 1, 1]\) равна \(0 - (-1) + 1 = 2\).
- Сумма значений \(s_i\) по всем отрезкам из разбиения должна быть равна нулю.
Обратите внимание, каждое \(s_i\) не обязано равняться 0, условие стоит только на сумму \(s_i\) по всем отрезкам разбиения.
Набор отрезков \([l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]\) называется разбиением массива \(a\) длины \(n\), если \(1 = l_1 \le r_1, l_2 \le r_2, \ldots, l_k \le r_k = n\), причем для всех \(i = 1, 2, \ldots k-1\) выполняется \(r_i + 1 = l_{i+1}\). Иными словами, каждый элемент массива должен принадлежать ровно одному отрезку.
Требуется предъявить разбиение массива, обладающее описанными свойствами, или сказать, что такого разбиения не существует.
Обратите внимание, минимизировать количество отрезков в разбиении не требуется.
Выходные данные
Для каждого набора входных данных выведите целое число \(k\) — количество отрезков в получившемся разбиении. Если требуемого разбиения не существует, выведите \(-1\).
Далее, если разбиение существует, то в \(i\)-й из следующих \(k\) строк выведите два целых числа \(l_i\) и \(r_i\) — границы \(i\)-го отрезка. При этом должны выполняться условия:
- \(l_i \le r_i\) для всех \(i\) от \(1\) до \(k\).
- \(l_{i + 1} = r_i + 1\) для всех \(i\) от \(1\) до \((k - 1)\).
- \(l_1 = 1, r_k = n\).
Если существует несколько корректных разбиений массива на отрезки, разрешается вывести любое из них.
Примечание
В первом наборе входных данных массив можно разбить на один отрезок длины \(4\). Сумма на этом отрезке будет равна \(1 - 1 + 1 - 1 = 0\).
Во втором наборе входных данных массив можно разбить на два отрезка длины \(3\). В первом из них знакопеременная сумма будет равна \(-1 -1 + 1 = -1\), а во втором: \(1 - 1 + 1 = 1\). Получаем общую сумму: \(-1 + 1 = 0\).
В третьем и четвертом наборах входных данных можно показать, что требуемого разбиения не существует.