Приховане Дерево
Розгляньте бінарне дерево, в якому листки мають цілі ваги. Таке дерево називається збалансованим, якщо для кожного вузла, що не є листком, сума ваг у його лівому піддереві дорівнює сумі ваг у правому піддереві. Наприклад, дерево на наступному рисунку є збалансованим.
Рисунок 1. Збалансоване дерево
Збалансоване дерево вважається прихованим у послідовності A, якщо цілі числа, отримані шляхом перерахування ваг усіх листків дерева зліва направо, утворюють підпослідовність A. Підпослідовність — це послідовність, яку можна отримати, видаливши нуль або більше елементів з оригінальної послідовності без зміни порядку решти елементів.
Наприклад, збалансоване дерево на рисунку вище приховане в послідовності 3 4 1 3 1 2 4 4 6, тому що 4 1 1 2 4 4 є його підпослідовністю.
Ваше завдання — знайти в заданій послідовності цілих чисел збалансоване дерево з найбільшою кількістю листків, яке приховане в ній. Насправді, дерево, показане на Рисунку 1, має найбільшу кількість листків серед збалансованих дерев, прихованих у згаданій вище послідовності.
Вхідні дані
Вхід складається з кількох наборів даних. Кожен набір даних представляє послідовність A цілих чисел у форматі
N
A_1 A_2 ... A_N
де 1 ≤ N ≤ 1000 і 1 ≤ A_i ≤ 500 для 1 ≤ i ≤ N. N — це довжина вхідної послідовності, а A_i — це i-й елемент послідовності.
Вхід закінчується рядком, що складається з одного нуля. Кількість наборів даних не перевищує 50.
Вихідні дані
Для кожного набору даних знайдіть збалансоване дерево з найбільшою кількістю листків серед тих, що приховані в A, і виведіть у рядку кількість його листків.