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을 출력한다. 그 외의 경우는 사전식 순서로 주어진 표시 코드 이전에 오는 표시 코드를 출력한다.