Як відомо, нещодавно Україна подала заявку на проведення зимових Олімпійських ігор 2022 року. Щоб збільшити шанси перемоги цієї заявки над іншими, нам потрібно спроектувати якнайдосконаліші олімпійські об’єкти. Одним із таких об’єктів є лижна траса, яку прокладатимуть уздовж фрагмента вузького плоскогір’я. Плоскогір’я є низкою пологих підйомів і спусків. Якщо його розбити на ділянки завдовжки 1 км, кожну ділянку можна охарактеризувати як підйом або як спуск. На оптимальній для спортсменів трасі кількість ділянок-підйомів і кількість ділянок-спусків мають збігатися.
Знаючи, в якій послідовності йдуть підйоми і спуски плоскогір’я, визначте довжину найдовшої потенційної траси, тобто такого фрагмента плоскогір’я, що містить однакову кількість підйомів і спусків.
У першому рядку вказано натуральне число n
- кількість кілометрових ділянок плоскогір’я. У другому рядку записано n
чисел, що задають рельєф плоскогір’я. Кожне з цих чисел - або одиниця (підйом), або нуль (спуск). Плоскогір’я не є круглим, тобто перша та остання його ділянки не сполучені між собою.
У ≈ 40 % тестів 2 ≤ n ≤ 100
.
У ≈ 30 % тестів 100 < n ≤ 10000
.
У ≈ 30 % тестів 10000 < n ≤ 1000000
.
Вивести довжину в кілометрах найдовшого фрагмента плоскогір’я, що містить однакову кількість підйомів і спусків. Якщо жодного такого фрагмента немає, виведіть число 0.
Пояснення до прикладів
У першому прикладі фрагмент 1 1 0 0 довжини 4 містить по два підйоми та спуски. Таку саму властивість має і фрагмент 1 0 0 1. Довших фрагментів, що містять однакову кількість підйомів і спусків, задана послідовність не має.
У другому прикладі фрагмент 0 1 довжини 2 містить по одному підйому і спуску. Довших фрагментів із рівною кількістю підйомів і спусків немає.
У третьому прикладі, як видно, жоден фрагмент не містить однакової кількості підйомів і спусків.
У четвертому прикладі найдовшим фрагментом, що містить рівну кількість підйомів і спусків, є вся послідовність.