Prevtree

엄격 이진 트리는 단말 노드가 아닌 모든 노드가 정확히 두 자식 노드를 가지는 이진 트리이다. 어떤 노드의 단말값은 그 노드를 루트로 하는 부분 트리에 포함된 단말 노드의 개수이다.

아래 트리는 엄격 이진 트리이며, 각 노드에 적힌 수는 그 노드의 단말값이다.

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

이러한 트리를 전위 순회하면서 루트와 왼쪽 자식인 노드들의 단말값을 차례로 나열한다. 위 그림에서는 * 표시가 있는 노드들이 나열되며, 그 결과는 (7, 4, 1, 2, 1, 1, 1)이다. 이 수열을 그 트리의 표시 코드라고 한다.

엄격 이진 트리의 표시 코드가 주어졌을 때, 같은 개수의 단말 노드를 가지는 트리들 중에서 표시 코드가 사전식 순서로 주어진 표시 코드의 바로 앞에 오는 트리의 표시 코드를 구하시오.

첫째 줄에 표시 코드의 길이 L이 주어진다. 1 <= L <= 10,000이다.

둘째 줄에는 표시 코드를 나타내는 L개의 정수가 공백으로 구분되어 주어진다.

주어진 표시 코드가 사전식 순서로 가장 앞서는 표시 코드라면 0을 출력한다.

그렇지 않다면 사전식 순서로 주어진 표시 코드의 바로 앞에 오는 표시 코드를 출력한다.