숨은 트리

잎마다 정수 가중치가 붙은 이진 트리를 생각한다. 잎이 아닌 모든 노드에서 왼쪽 서브트리의 가중치 합과 오른쪽 서브트리의 가중치 합이 같으면, 그 트리를 균형 트리라고 부른다. 잎이 아닌 노드에는 왼쪽 자식과 오른쪽 자식이 모두 있다. 예를 들어 다음 그림의 트리는 균형 트리다.

그림 I.1. 균형 트리

균형 트리의 잎을 왼쪽에서 오른쪽으로 모두 읽어 만든 정수 열이 수열 $A$의 부분 수열이면, 그 균형 트리가 $A$에 숨어 있다고 한다. 여기서 부분 수열은 원래 수열에서 원소를 0개 이상 지우고 남은 원소의 순서를 그대로 유지한 수열이다.

그림 I.1의 균형 트리는 수열 3 4 1 3 1 2 4 4 6에 숨어 있다. 잎을 왼쪽에서 오른쪽으로 읽으면 4 1 1 2 4 4가 되고, 이 열이 그 수열의 부분 수열이기 때문이다.

주어진 정수 수열에 숨어 있는 균형 트리 중에서 잎이 가장 많은 것을 찾아라. 위 수열에서는 그림 I.1의 트리가 잎이 가장 많다.

입력은 테스트 케이스 여러 개로 이루어진다. 각 테스트 케이스는 정수 수열 $A$를 다음 형식으로 준다.

N
A1 A2 ... AN

$N$은 수열의 길이이고, $A_i$는 수열의 $i$번째 원소다. $1 \le N \le 1000$이고 $1 \le A_i \le 500$이다.

입력의 끝에는 0 하나만 있는 줄이 온다. 테스트 케이스는 50개를 넘지 않는다.

각 테스트 케이스마다 $A$에 숨어 있는 균형 트리 중 잎이 가장 많은 것을 찾아, 그 잎의 개수를 한 줄에 출력한다.