Скрытое дерево
Рассмотрим бинарное дерево, в котором листья имеют целочисленные веса. Такое дерево называется сбалансированным, если для каждого узла, не являющегося листом, сумма весов в его левом поддереве равна сумме весов в правом поддереве. Например, дерево на следующем рисунке является сбалансированным.
Рисунок 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, и выведите в строке количество его листьев.