#include "xylophone.h"
int A[5005];
int dif[5005];
// A[i] = dif(i, i+1);
void solve(int N) {
int mx = query(1,N);
int l = 1, r = N;
for(int i = 1; i < N; ++i) dif[i] = query(i,i+1);
while(l < r) { // move l
if(query(l+1,r) != mx) break;
++l;
}
while(l < r) { // move r
if(query(l,r-1) != mx) break;
--r;
}
A[l] = 1;
A[r] = N;
// l , or r is the lowest
int mx_dif = 0;
for(int i = l-1; i >= 0; --i) {
int dif = query(i,l);
if(dif > mx_dif) {
mx_dif = dif;
A[i] = 1 + dif;
}
else {
A[i] = A[i+1] - query(i,i+1);
}
}
mx_dif = 0;
for(int i = l+1; i < r; ++i) {
int dif = query(l, i);
if(dif > mx_dif) {
mx_dif = dif;
A[i] = 1 + dif;
}
else {
A[i] = A[i-1] - query(i-1, i);
}
}
mx_dif = 0;
for(int i = r+1; i <= N; ++i) {
int dif = query(l, i);
if(dif > mx_dif) {
mx_dif = dif;
A[i] = 1 + dif;
}
else {
A[i] = A[i-1] - query(i-1, i);
}
}
for(int i = 1; i <= N; i++) {
answer(i, A[i]);
}
}
