#include #include #include #include using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(n); i++) struct Block{ priority_queue, less> L; priority_queue, greater> R; void output(){ auto Lbuf = L; cout << "L : [ "; while(Lbuf.size()){ cout << Lbuf.top() << " "; Lbuf.pop(); } cout << "] "; auto Rbuf = R; cout << "R : [ "; while(Rbuf.size()){ cout << Rbuf.top() << " "; Rbuf.pop(); } cout << "] "; cout << endl; } }; Block merge_blocks(Block l, Block r){ if(l.L.size() < r.L.size()) swap(l,r); while(r.L.size()){ l.L.push(r.L.top()); r.L.pop(); l.R.push(r.R.top()); r.R.pop(); } while(l.L.top() > l.R.top()){ int lL = l.L.top(); l.L.pop(); int lR = l.R.top(); l.R.pop(); l.L.push(lR); l.R.push(lL); } return move(l); } int main() { int N; cin >> N; vector A(N); int preans = 0; vector blocks[2]; rep(t,2){ Block a; a.L.push(-2); a.R.push(-2); blocks[t].push_back(move(a)); } rep(i,N){ int a; cin >> a; a ^= preans; A[i] = a; // cout << "a = " << A[i] << endl; int t = i%2; auto& pblock = blocks[1-t].back(); if(pblock.L.top() > a) preans = pblock.L.top(); else preans = a; if(i == 0){ Block tmp; tmp.L.push(-1); tmp.R.push(a); blocks[t].push_back(move(tmp)); } else{ Block tmp; tmp.L.push(min(A[i-1], A[i])); tmp.R.push(max(A[i-1], A[i])); while(true){ if(blocks[t].back().R.top() < tmp.L.top()) break; tmp = merge_blocks(blocks[t].back(), tmp); blocks[t].pop_back(); } blocks[t].push_back(move(tmp)); } cout << preans << "\n"; //cout << "process : " << endl; cout << endl; //rep(t,2){ for(auto& a : blocks[t]) a.output(); cout << endl; } //cout << endl << endl; } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;