Hidden Tree

Time limit5sMemory limit128 MB

Summary

Find the longest subsequence that forms the leaves of a binary tree where each internal node has equal left and right sums.

Level: Hard8 of 10
Topics: Dynamic programming, Tree, Divide and conquer
Solved: No attempts yet

Problem

Consider a binary tree whose leaves carry integer weights. The tree is balanced when the weights in the left subtree of every non-leaf node sum to the same value as the weights in its right subtree. Every non-leaf node has both a left child and a right child. For example, the tree in the figure below is balanced.

Figure I.1. A balanced tree

A balanced tree is hidden in a sequence $A$ when the weights of all its leaves, read from left to right, form a subsequence of $A$ . A subsequence is what is left after deleting zero or more elements from the original sequence, keeping the order of the remaining elements.

The balanced tree in Figure I.1 is hidden in the sequence 3 4 1 3 1 2 4 4 6. Its leaves read 4 1 1 2 4 4 from left to right, and that is a subsequence of the sequence.

Given a sequence of integers, find the balanced tree hidden in it with the largest number of leaves. For the sequence above, the tree in Figure I.1 has the most leaves.

Input

The input consists of several test cases. Each test case gives one sequence $A$ of integers in the format

N
A1 A2 ... AN

where $N$ is the length of the sequence and $A_i$ is its $i$ -th element, with $1 \le N \le 1000$ and $1 \le A_i \le 500$ .

A line holding a single zero ends the input. The number of test cases is at most 50.

Output

For each test case, find the balanced tree hidden in $A$ with the largest number of leaves and print the number of its leaves in one line.

Examples1

Example 1

Input

9
3 4 1 3 1 2 4 4 6
4
3 12 6 3
10
10 9 8 7 6 5 4 3 2 1
11
10 9 8 7 6 5 4 3 2 1 1
8
1 1 1 1 1 1 1 1
0

Expected output