2269번 - Prevtree

문제

Strict Binary Tree는 이진 트리의 일종으로, 단말 노드가 아닌 모든 노드들이 두 자식 노드를 가지고 있는 트리이다. Strict Binary Tree의 단말값은 그 노드를 루트로 하는 부분 트리에 있는 단말 노드의 개수이다. 예를 들어 아래와 같은 트리는 Strict Binary Tree이며, 노드의 위치에 있는 각각의 수는 그 노드의 단말값이다.

 *7 
 / \ 
 / \ 
 / \ 
 *4 3 
 / \ / \ 
*1 3 *1 2 
 / \ / \ 
 *2 1 *1 1
 / \ 
*1 1 

이와 같은 Strict Binary Tree를 Preorder(전위)로 돌면서, 루트와 어떤 노드의 왼쪽 자식 노드들의 단말값을 나열하면 (7, 4, 1, 2, 1, 1, 1)과 같이 된다. 위의 그림에서는 *표가 된 노드들이 단말값이 나열되는 노드들이다. 이와 같이 단말값을 나열한 것을 그 트리의 표시 코드라고 하자.

어떤 Strict Binary Tree의 표시 코드가 주어졌을 때, 이 트리와 같은 개수의 단말 노드를 가지면서 표시 코드가 사전식 순서로 주어진 표시 코드 이전에 오는 트리를 구하시오.

입력

첫째 줄에 표시 코드의 길이 L(1 ≤ L ≤ 10,000)이 주어진다. 다음 줄에는 표시 코드를 나타내는 L개의 정수들이 공백으로 분리되어 주어진다.

출력

만약 주어진 표시 코드가 사전식 순서로 제일 앞에 오는 표시 코드라면 0을 출력한다. 그 외의 경우는 사전식 순서로 주어진 표시 코드 이전에 오는 표시 코드를 출력한다.

제한

힌트