#include "xylophone.h" #include <bits/stdc++.h> using namespace std; static int a[5005]; int dp[5005][5005], pos[5005], cnt[5005]; bool was[5005]; int ask(int l, int r){ if(dp[l][r]) return dp[l][r]; return dp[l][r] = query(l, r); } void solve(int n){ for(int r = 2; r <= n; r++){ bool ok = 1; int l = r - 1; a[r] = n, was[a[r]] = 1; a[l] = n - ask(l, r), was[a[l]] = 1; if(r < n) a[r + 1] = n - ask(r, r + 1), was[a[r + 1]] = 1; for(int i = l - 1; i >= 1; i--){ a[i] = a[i + 1] - ask(i, i + 1); if(a[i] < 0 || a[i] > n || was[a[i]]){ a[i] = a[i + 1] + ask(i, i + 1); was[a[i]] = 1; continue; } if(ask(i, i + 1) == abs(a[i + 1] - a[i]) && ask(i, i + 2) == max({a[i], a[i + 1], a[i + 2]}) - min({a[i], a[i + 1], a[i + 2]}) && ask(i + 1, i + 2) == abs(a[i + 2] - a[i + 1])){ was[a[i]] = 1; continue; } a[i] = a[i + 1] + ask(i, i + 1); was[a[i]] = 1; } for(int i = r + 2; i <= n; i++){ a[i] = a[i - 1] - ask(i - 1, i); if(a[i] < 0 || a[i] > n || was[a[i]]){ a[i] = a[i - 1] + ask(i - 1, i); was[a[i]] = 1; continue; } if(ask(i - 1, i) == abs(a[i] - a[i - 1]) && ask(i - 2, i) == max({a[i], a[i - 1], a[i - 2]}) - min({a[i], a[i - 1], a[i - 2]}) && ask(i - 2, i - 1) == abs(a[i - 2] - a[i - 1])){ was[a[i]] = 1; continue; } a[i] = a[i - 1] + ask(i - 1, i); was[a[i]] = 1; } for(int i = 2; i <= n; i++){ if(abs(a[i] - a[i - 1]) != ask(i - 1, i)) ok = 0; if(i >= 3 && max({a[i], a[i - 1], a[i - 2]}) - min({a[i], a[i - 1], a[i - 2]}) != ask(i - 2, i)) ok = 0; } for(int i = 1; i <= n; i++) ok &= (a[i] <= n), ok &= (a[i] >= 1); if(ok){ for(int i = 1; i <= n; i++) cnt[i] = 0; for(int i = 1; i <= n; i++) pos[a[i]] = i, cnt[a[i]]++; for(int i = 1; i <= n; i++) ok &= (cnt[i] == 1); ok &= (pos[1] < pos[n]); } if(ok) break; for(int i = 0; i <= n + 1; i++) was[i] = a[i] = pos[i] = 0; } for(int i = 1; i <= n; i++){ answer(i, a[i]); } }