#include "xylophone.h"
#include <vector>
#include <iostream>
using namespace std;
/*
5
2 1 5 3 4
10
7 6 3 9 2 8 5 1 10 4
*/
void solve(int N) {
int K = query(1,N);
int minIndex;{
int m, k;
int left, right;
left = 1;
right = N-1;
while(left != right){
m = (left+right)/2+1;
k = query(m, N);
if(k == K) left = m;
else right = m-1;
}
minIndex = left;
}
vector<bool> UsedNumbers(N+1, false);
vector<int> kVtr(N+1);
for(int i = 2; i <= N; ++i)
kVtr[i] = query(i-1,i);
vector<int> Solution(N+1);
Solution[minIndex] = 1;
UsedNumbers[Solution[minIndex]] = true;
Solution[minIndex+1] = Solution[minIndex] + kVtr[minIndex+1];
UsedNumbers[Solution[minIndex+1]] = true;
if(minIndex != 1){
Solution[minIndex-1] = Solution[minIndex] + kVtr[minIndex];
UsedNumbers[Solution[minIndex+1]] = true;
}
int k, kM, km, k_;
///After minIndex
for(int i = minIndex+2; i <= N; ++i){
k = kVtr[i];
kM = Solution[i-1] + k;
km = Solution[i-1] - k;
if((km < 1) || (UsedNumbers[km])){Solution[i] = kM; continue;}
if((kM > N) || (UsedNumbers[kM])){Solution[i] = km; continue;}
k_ = query(i-2,i);
Solution[i] = Solution[i-1];
if(Solution[i-2] < Solution[i-1]){ ///^
if(kVtr[i-1]+kVtr[i] == k_) Solution[i] += k; ///^^
else Solution[i] -= k; ///^v
}else{ ///v
if(kVtr[i-1]+kVtr[i] == k_) Solution[i] -= k; ///vv
else Solution[i] += k; ///v^
}
}
///Before minIndex
for(int i = minIndex-2; i >= 1; --i){
k = kVtr[i+1];
kM = Solution[i+1] + k;
km = Solution[i+1] - k;
if((km < 1) || (UsedNumbers[km])){Solution[i] = kM; continue;}
if((kM > N) || (UsedNumbers[kM])){Solution[i] = km; continue;}
k_ = query(i,i+2);
Solution[i] = Solution[i+1];
if(Solution[i+1] < Solution[i+2]){ ///v
if(kVtr[i+1]+kVtr[i+2] == k_)
Solution[i] -= k; ///vv
else
Solution[i] += k; ///v^
}else{ ///^
if(kVtr[i+1]+kVtr[i+2] == k_)
Solution[i] += k; ///^^
else
Solution[i] -= k; ///^v
}
}
// cout << "minindex=" << minIndex << " maxindex=" << maxIndex << endl;
// cout << "Solution:" << endl;
// for(int i = 1; i <= N; ++i)
// cout << Solution[i] << " ";
// cout << endl;
for(int i = 1; i <= N; i++)
answer(i, Solution[i]);
}
