#include <bits/stdc++.h>
#include "popa.h"
using namespace std;
int nxt[1005]; vector<int> st;
int lo[1005], hi[1005];
int query(int a, int b, int c, int d);
int build(int l, int r) {
if (l > r) return -1;
int rt = l;
while (nxt[rt] <= r) rt = nxt[rt];
lo[rt] = build(l, rt - 1);
hi[rt] = build(rt + 1, r);
return rt;
}
int solve(int N, int* left, int* right) {
for (int i = 0; i < N; i++) {
while (!st.empty() && query(i, i, i, st.back())) {
nxt[st.back()] = i;
st.pop_back();
}
}
while (!st.empty()) {
nxt[st.back()] = 1e5;
st.pop_back();
}
int rt = build(0, N - 1);
for (int i = 0; i < N; i++) left[i] = lo[i], right[i] = hi[i];
return rt;
}
