#include <bits/stdc++.h>
using namespace std;
#include "xylophone.h"
//#define int long long
static int A[5000];
void solve(int n) {
vector<array<int,2>>fark(n+1);
fark[n-1][0]=query(n-1,n);
for(int i=1;i<n-1;i++) {
fark[i][0]=query(i,i+1);
fark[i][1]=query(i,i+2);
}
vector<bool>cs(n+1);
//ilk yön +
cs[1]=1;
int toplam=0;
int mx=0;
int mn=0;
int mxi=1;
int mni=1;
for(int i=1;i<n-1;i++){
if(fark[i][1]==fark[i+1][0]+fark[i][0])cs[i+1]=cs[i];
else cs[i+1]=(1^cs[i]);
}
for(int i=1;i<=n-1;i++){
if(cs[i])toplam+=fark[i][0];
else toplam-=fark[i][0];
if(mx<toplam){
mx=toplam;
mxi=i+1;
}
if(mn>toplam){
mn=toplam;
mni=i+1;
}
}
if(mni<mxi){
int ansid=n-mx;
answer(1,ansid);
for(int i=1;i<n;i++){
if(!cs[i])ansid-=fark[i][0];
else ansid+=fark[i][0];
answer(i+1,ansid);
}
}
//ilk yön -
else{
cs[1]=0;
//int toplam=0;
mx=0;
toplam=0;
for(int i=1;i<n-1;i++){
if(fark[i][1]==fark[i+1][0]+fark[i][0])cs[i+1]=cs[i];
else cs[i+1]=(1^cs[i]);
}
for(int i=1;i<=n-1;i++){
if(cs[i])toplam+=fark[i][0];
else toplam -=fark[i][0];
mx=max(toplam,mx);
}
int ansid=n-mx;
answer(1,ansid);
for(int i=1;i<n;i++){
if(!cs[i])ansid-=fark[i][0];
else ansid+=fark[i][0];
answer(i+1,ansid);
}
}
}
