Задача Validity Справедливою будемо називати послідовність з нулів та одиниць, якщо на парних місцях послідовності кількість одиниць співпадає з кількістю одиниць на непарних. Наприклад, послідовність 011011 є справедливою, а послідовність 011101 – ні. Задано послідовність непарної довжини з нулів та одиниць, з якої можна видалити одну цифру. Яку цифру треба видалити, щоб послідовність стала справедливою? Наприклад, з послідовності 0111011 можна видалити другу цифру.
Технічні умови. Напишіть програму Validity, яка читає з клавіатури кількість чисел в послідовності, а далі - послідовність непарної довжини з нулів та одиниць. Довжина послідовності не перевищує 200001. Всі числа розділено пропусками. Програма повинна вивести на екран одне число – номер цифри в послідовності, яку треба видалити, щоб послідовність стала справедливою. Нумерація цифр розпочинається з 1. Якщо розв’язок неможливий – програма повинна вивести 0. Якщо розв’язків кілька – програма виводить найменший номер цифри з послідовності, яку треба вилучити.
|
Приклади |
|
Введення: |
Виведення: |
Приклад 1 |
|
7 0 1 1 1 0 1 1
|
2
|
Приклад 2
|
|
7 0 0 0 0 0 0 0
|
1
|