/** * date : 2021-12-15 01:42:55 */ #define NDEBUG using namespace std; // intrinstic #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // utility namespace Nyaan { using ll = long long; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; template using V = vector; template using VV = vector>; using vi = vector; using vl = vector; using vd = V; using vs = V; using vvi = vector>; using vvl = vector>; template struct P : pair { template P(Args... args) : pair(args...) {} using pair::first; using pair::second; T &x() { return first; } const T &x() const { return first; } U &y() { return second; } const U &y() const { return second; } P &operator+=(const P &r) { first += r.first; second += r.second; return *this; } P &operator-=(const P &r) { first -= r.first; second -= r.second; return *this; } P &operator*=(const P &r) { first *= r.first; second *= r.second; return *this; } P operator+(const P &r) const { return P(*this) += r; } P operator-(const P &r) const { return P(*this) -= r; } P operator*(const P &r) const { return P(*this) *= r; } P operator*(int r) const { return {first * r, second * r}; } P operator-() const { return P{-first, -second}; } }; using pl = P; using pi = P; using vp = V; constexpr int inf = 1001001001; constexpr long long infLL = 4004004004004004004LL; template int sz(const T &t) { return t.size(); } template inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; } template inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; } template inline T Max(const vector &v) { return *max_element(begin(v), end(v)); } template inline T Min(const vector &v) { return *min_element(begin(v), end(v)); } template inline long long Sum(const vector &v) { return accumulate(begin(v), end(v), 0LL); } template int lb(const vector &v, const T &a) { return lower_bound(begin(v), end(v), a) - begin(v); } template int ub(const vector &v, const T &a) { return upper_bound(begin(v), end(v), a) - begin(v); } constexpr long long TEN(int n) { long long ret = 1, x = 10; for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1); return ret; } template pair mkp(const T &t, const U &u) { return make_pair(t, u); } template vector mkrui(const vector &v, bool rev = false) { vector ret(v.size() + 1); if (rev) { for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1]; } else { for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i]; } return ret; }; template vector mkuni(const vector &v) { vector ret(v); sort(ret.begin(), ret.end()); ret.erase(unique(ret.begin(), ret.end()), ret.end()); return ret; } template vector mkord(int N, F f) { vector ord(N); iota(begin(ord), end(ord), 0); sort(begin(ord), end(ord), f); return ord; } template vector mkinv(vector &v) { int max_val = *max_element(begin(v), end(v)); vector inv(max_val + 1, -1); for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i; return inv; } } // namespace Nyaan // bit operation namespace Nyaan { __attribute__((target("popcnt"))) inline int popcnt(const u64 &a) { return _mm_popcnt_u64(a); } inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; } inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; } inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; } template inline int gbit(const T &a, int i) { return (a >> i) & 1; } template inline void sbit(T &a, int i, bool b) { if (gbit(a, i) != b) a ^= T(1) << i; } constexpr long long PW(int n) { return 1LL << n; } constexpr long long MSK(int n) { return (1LL << n) - 1; } } // namespace Nyaan // inout namespace Nyaan { template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &... u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &... u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &... u) { cout << t; outr(u...); } struct IoSetupNya { IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7); } } iosetupnya; } // namespace Nyaan // debug namespace DebugImpl { template struct is_specialize : false_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize< U, typename conditional::type> : true_type {}; template struct is_specialize::value, void>> : true_type { }; void dump(const char& t) { cerr << t; } void dump(const string& t) { cerr << t; } void dump(const bool& t) { cerr << (t ? "true" : "false"); } template ::value, nullptr_t> = nullptr> void dump(const U& t) { cerr << t; } template void dump(const T& t, enable_if_t::value>* = nullptr) { string res; if (t == Nyaan::inf) res = "inf"; if constexpr (is_signed::value) { if (t == -Nyaan::inf) res = "-inf"; } if constexpr (sizeof(T) == 8) { if (t == Nyaan::infLL) res = "inf"; if constexpr (is_signed::value) { if (t == -Nyaan::infLL) res = "-inf"; } } if (res.empty()) res = to_string(t); cerr << res; } template void dump(const pair&); template void dump(const pair&); template void dump(const T& t, enable_if_t::value>* = nullptr) { cerr << "[ "; for (auto it = t.begin(); it != t.end();) { dump(*it); cerr << (++it == t.end() ? "" : ", "); } cerr << " ]"; } template void dump(const pair& t) { cerr << "( "; dump(t.first); cerr << ", "; dump(t.second); cerr << " )"; } template void dump(const pair& t) { cerr << "[ "; for (int i = 0; i < t.second; i++) { dump(t.first[i]); cerr << (i == t.second - 1 ? "" : ", "); } cerr << " ]"; } void trace() { cerr << endl; } template void trace(Head&& head, Tail&&... tail) { cerr << " "; dump(head); if (sizeof...(tail) != 0) cerr << ","; trace(forward(tail)...); } } // namespace DebugImpl #ifdef NyaanDebug #define trc(...) \ do { \ cerr << "## " << #__VA_ARGS__ << " = "; \ DebugImpl::trace(__VA_ARGS__); \ } while (0) #else #define trc(...) (void(0)) #endif // macro #define each(x, v) for (auto&& x : v) #define each2(x, y, v) for (auto&& [x, y] : v) #define all(v) (v).begin(), (v).end() #define rep(i, N) for (long long i = 0; i < (long long)(N); i++) #define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--) #define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++) #define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--) #define reg(i, a, b) for (long long i = (a); i < (b); i++) #define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--) #define fi first #define se second #define ini(...) \ int __VA_ARGS__; \ in(__VA_ARGS__) #define inl(...) \ long long __VA_ARGS__; \ in(__VA_ARGS__) #define ins(...) \ string __VA_ARGS__; \ in(__VA_ARGS__) #define in2(s, t) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i]); \ } #define in3(s, t, u) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i]); \ } #define in4(s, t, u, v) \ for (int i = 0; i < (int)s.size(); i++) { \ in(s[i], t[i], u[i], v[i]); \ } #define die(...) \ do { \ Nyaan::out(__VA_ARGS__); \ return; \ } while (0) namespace Nyaan { void solve(); } int main() { Nyaan::solve(); } // #define protected public template struct LazyReversibleBBST : Tree { using Tree::merge; using Tree::split; using typename Tree::Ptr; LazyReversibleBBST() = default; void toggle(Ptr t) { swap(t->l, t->r); t->sum = ts(t->sum); t->rev ^= true; } T fold(Ptr &t, int a, int b) { auto x = split(t, a); auto y = split(x.second, b - a); auto ret = sum(y.first); t = merge(x.first, merge(y.first, y.second)); return ret; } void reverse(Ptr &t, int a, int b) { auto x = split(t, a); auto y = split(x.second, b - a); toggle(y.first); t = merge(x.first, merge(y.first, y.second)); } void apply(Ptr &t, int a, int b, const E &e) { auto x = split(t, a); auto y = split(x.second, b - a); propagate(y.first, e); t = merge(x.first, merge(y.first, y.second)); } protected: inline T sum(const Ptr t) { return t ? t->sum : T(); } Ptr update(Ptr t) override { if (!t) return t; t->cnt = 1; t->sum = t->key; if (t->l) t->cnt += t->l->cnt, t->sum = f(t->l->sum, t->sum); if (t->r) t->cnt += t->r->cnt, t->sum = f(t->sum, t->r->sum); return t; } void push(Ptr t) override { if (!t) return; if (t->rev) { if (t->l) toggle(t->l); if (t->r) toggle(t->r); t->rev = false; } if (t->lazy != E()) { if (t->l) propagate(t->l, t->lazy); if (t->r) propagate(t->r, t->lazy); t->lazy = E(); } } void propagate(Ptr t, const E &x) { t->lazy = h(t->lazy, x); t->key = g(t->key, x); t->sum = g(t->sum, x); } }; /** * @brief 遅延伝搬反転可能平衡二分木(基底クラス) */ template struct SplayTreeBase { using Ptr = Node *; template Ptr my_new(const Args &... args) { return new Node(args...); } void my_del(Ptr p) { delete p; } bool is_root(Ptr t) { return !(t->p) || (t->p->l != t && t->p->r != t); } int size(Ptr t) const { return count(t); } virtual void splay(Ptr t) { push(t); while (!is_root(t)) { Ptr q = t->p; if (is_root(q)) { push(q), push(t); rot(t); } else { Ptr r = q->p; push(r), push(q), push(t); if (pos(q) == pos(t)) rot(q), rot(t); else rot(t), rot(t); } } } Ptr get_left(Ptr t) { while (t->l) push(t), t = t->l; return t; } Ptr get_right(Ptr t) { while (t->r) push(t), t = t->r; return t; } pair split(Ptr t, int k) { if (!t) return {nullptr, nullptr}; if (k == 0) return {nullptr, t}; if (k == count(t)) return {t, nullptr}; push(t); if (k <= count(t->l)) { auto x = split(t->l, k); t->l = x.second; t->p = nullptr; if (x.second) x.second->p = t; return {x.first, update(t)}; } else { auto x = split(t->r, k - count(t->l) - 1); t->r = x.first; t->p = nullptr; if (x.first) x.first->p = t; return {update(t), x.second}; } } Ptr merge(Ptr l, Ptr r) { if (!l && !r) return nullptr; if (!l) return splay(r), r; if (!r) return splay(l), l; splay(l), splay(r); l = get_right(l); splay(l); l->r = r; r->p = l; update(l); return l; } using Key = decltype(Node::key); Ptr build(const vector &v) { return build(0, v.size(), v); } Ptr build(int l, int r, const vector &v) { if (l + 1 >= r) return my_new(v[l]); return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v)); } template void insert(Ptr &t, int k, const Args &... args) { splay(t); auto x = split(t, k); t = merge(merge(x.first, my_new(args...)), x.second); } void erase(Ptr &t, int k) { splay(t); auto x = split(t, k); auto y = split(x.second, 1); my_del(y.first); t = merge(x.first, y.second); } virtual Ptr update(Ptr t) = 0; protected: inline int count(Ptr t) const { return t ? t->cnt : 0; } virtual void push(Ptr t) = 0; Ptr build(const vector &v) { return build(0, v.size(), v); } Ptr build(int l, int r, const vector &v) { if (l + 1 >= r) return v[l]; return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v)); } inline int pos(Ptr t) { if (t->p) { if (t->p->l == t) return -1; if (t->p->r == t) return 1; } return 0; } virtual void rot(Ptr t) { Ptr x = t->p, y = x->p; if (pos(t) == -1) { if ((x->l = t->r)) t->r->p = x; t->r = x, x->p = t; } else { if ((x->r = t->l)) t->l->p = x; t->l = x, x->p = t; } update(x), update(t); if ((t->p = y)) { if (y->l == x) y->l = t; if (y->r == x) y->r = t; } } }; /** * @brief Splay Tree(base) */ template struct LazyReversibleSplayTreeNode { using Ptr = LazyReversibleSplayTreeNode *; Ptr l, r, p; T key, sum; E lazy; int cnt; bool rev; LazyReversibleSplayTreeNode(const T &t = T(), const E &e = E()) : l(), r(), p(), key(t), sum(t), lazy(e), cnt(1), rev(false) {} }; template struct LazyReversibleSplayTree : LazyReversibleBBST>, LazyReversibleSplayTreeNode, T, E, f, g, h, ts> { using Node = LazyReversibleSplayTreeNode; }; /** * @brief 遅延伝搬反転可能Splay Tree */ template struct ReversibleBBST : Tree { using Tree::merge; using Tree::split; using typename Tree::Ptr; ReversibleBBST() = default; virtual void toggle(Ptr t) { swap(t->l, t->r); t->sum = ts(t->sum); t->rev ^= true; } T fold(Ptr &t, int a, int b) { auto x = split(t, a); auto y = split(x.second, b - a); auto ret = sum(y.first); t = merge(x.first, merge(y.first, y.second)); return ret; } void reverse(Ptr &t, int a, int b) { auto x = split(t, a); auto y = split(x.second, b - a); toggle(y.first); t = merge(x.first, merge(y.first, y.second)); } Ptr update(Ptr t) override { if (!t) return t; t->cnt = 1; t->sum = t->key; if (t->l) t->cnt += t->l->cnt, t->sum = f(t->l->sum, t->sum); if (t->r) t->cnt += t->r->cnt, t->sum = f(t->sum, t->r->sum); return t; } protected: inline T sum(const Ptr t) { return t ? t->sum : T(); } void push(Ptr t) override { if (!t) return; if (t->rev) { if (t->l) toggle(t->l); if (t->r) toggle(t->r); t->rev = false; } } }; /** * @brief 反転可能平衡二分木(基底クラス) */ template struct ReversibleSplayTreeNode { using Ptr = ReversibleSplayTreeNode *; Ptr l, r, p; T key, sum; int cnt; bool rev; ReversibleSplayTreeNode(const T &t = T()) : l(), r(), p(), key(t), sum(t), cnt(1), rev(false) {} }; template struct ReversibleSplayTree : ReversibleBBST>, ReversibleSplayTreeNode, T, f, ts> { using Node = ReversibleSplayTreeNode; }; /** * @brief 反転可能Splay Tree */ using namespace Nyaan; namespace HELP { pl f(pl a, pl b) { return max(a, b); } pl g(pl a, ll b) { return pl{a.fi + b, a.se}; } ll h(ll a, ll b) { return a + b; } pl ts(pl a) { return a; } using BBST = LazyReversibleSplayTree; } // namespace HELP void Nyaan::solve() { inl(N); ll pre = 0; HELP::BBST tree; typename HELP::BBST::Node* root = tree.build(vp{{-inf, inf*2}}); rep(i, N) { inl(A); A ^= pre; auto lwb = [&](auto rc, decltype(root) r, int x) -> int { //tree.push(r); //tree.update(r); if (r->key.second >= x) { return r->l ? rc(rc, r->l, x) : 0; } ll res = (r->l ? r->l->cnt : 0) + 1; return res + (r->r ? rc(rc, r->r, x) : 0); }; int u = lwb(lwb, root, A); trc(i, u); int mn = u == i ? -inf : tree.fold(root, u, i).first; int sc = max(0, mn + 1); if (0 != u) tree.apply(root, 0, u, 1); if (u != i) tree.apply(root, u, i, -1); tree.insert(root, u, pl{sc, A}); ll ans = A; auto dfs = [&](auto rc, decltype(root) r) -> void { tree.push(r); if (r->key.first >= 0) amax(ans, r->key.second); if (r->r and r->r->sum.first >= 0) { rc(rc, r->r); } else { if (r->l and r->l->sum.first >= 0) { rc(rc, r->l); } } }; dfs(dfs, root); out(ans); pre = ans; } }