#include<bits/stdc++.h>
#include<popa.h>
using namespace std;
stack<int> open,idle;
int n_,in_;
int ask(int a,int b,int c,int d)
{
while(a>b);
while(c>d);
in_++;
return query(a,b,c,d);
}
int solve(int N, int* Left, int* Right)
{
n_=N;
in_=0;
for(int i=0;i<N;i++)Left[i]=0,Right[i]=0;
open=idle;
Left[0]=-1;
open.push(0);
for(int i=1;i<N;i++)
{
int prev=-1;
while(open.size()&&ask(open.top(),i,i,i))
{
prev=open.top();
open.pop();
}
Left[i]=prev;
open.push(i);
}
int prev=-1;
while(open.size())
{
Right[open.top()]=prev;
prev=open.top();
open.pop();
}
open=idle;
Right[N-1]=-1;
open.push(N-1);
for(int i=N-2;i>=0;i--)
{
int prev=-1;
if(Right[i])
{
while(open.top()!=Right[i])
open.pop();
prev=Right[i];
}
else
while(open.size()&&Left[open.top()]!=i&&ask(i,open.top(),i,i))
{
prev=open.top();
open.pop();
}
Right[i]=prev;
open.push(i);
}
set<int> seen={};
for(int i=0;i<N;i++)
{
seen.insert(Left[i]);
seen.insert(Right[i]);
}
assert(in_<=3*N);
for(int i=0;i<N;i++)
if(seen.count(i)==0)return i;
assert(0==1);
}
