Як відомо, нещодавно Україна подала заявку на проведення зимових Олімпійських ігор 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 содержит по одному подъему и спуску. Более длинных фрагментов с равным количеством подъемов и спусков нет.
В третьем примере ни один из фрагментов не содержит одинакового количества подъемов и спусков.
В четвертом примере самым длинным фрагментом, содержащим равное количество подъемов и спусков, является вся последовательность.