#include<bits/stdc++.h>
#include "popa.h"
using namespace std ;
int query ( int a , int b , int c , int d ) ;
pair < int , int > ranges[ 1007 ] ;
vector < int > v ;
int solve ( int n , int *Left , int *Right ) {
for ( int i = 0 ; i < n ; ++ i ) {
ranges[ i ] = { i , i } ;
Left[ i ] = Right[ i ] = -1 ;
}
v.clear ( ) ;
v.push_back ( -1 ) ;
for ( int i = 0 ; i < n ; ++ i ) {
while ( 1 ) {
int aux = v.back ( ) ;
if ( aux >= 0 && query ( aux , i , i , i ) == 1 ) {
v.pop_back ( ) ;
}
else {
ranges[ i ].first = aux + 1 ;
for ( auto y : v ) {
if ( y != -1 ) {
ranges[ y ].second = i ;
}
}
break ;
}
}
v.push_back ( i ) ;
}
int root = -1 ;
for ( int i = 0 ; i < n ; ++ i ) {
if ( ranges[ i ].first == 0 && ranges[ i ].second == n - 1 ) {
root = i ;
break ;
}
}
stack < int > aux ;
aux.push ( root ) ;
while ( aux.empty ( ) == false ) {
int wh = aux.top ( ) ;
aux.pop ( ) ;
for ( int i = 0 ; i < n ; ++ i ) {
if ( ranges[ i ].first == ranges[ wh ].first && ranges[ i ].second == wh - 1 ) {
Left[ wh ] = i ;
}
if ( ranges[ i ].first == wh + 1 && ranges[ i ].second == ranges[ wh ].second ) {
Right[ wh ] = i ;
}
}
if ( Left[ wh ] != -1 ) {
aux.push ( Left[ wh ] ) ;
}
if ( Right[ wh ] != -1 ) {
aux.push ( Right[ wh ] ) ;
}
}
return root ;
}
