{"raw_statement":[{"iden":"statement","content":"There is a party in town and you would like to attend it. The party theme is bitwise operations! You just knocked on the door and the bodyguard with a big xor-like hat on his head asks you a question in order to let you in. You just heard your favourite song \"Se misca pe bit\" playing inside, so you need to solve the problem as quick as possible. \n\nYou are given a sequence of $1 <= N <= 10^6$ pairwise _distinct_ non-negative integers $a_1, a_2,..., a_N$. The value of a subsequence $a_i, a_{i + 1},..., a_j$ with $i <= j$ is: \n\n \n\nwhere OR is the bitwise OR operator.\n\nYou need to calculate the bitwise XOR sum of the values of all subsequences.\n\nThe first line of the input will contain the number $N$ ($1 <= N <= 10^6$), representing the size of the given sequence $a$.  The following line will contain $N$ pairwise _distinct_ non-negative integers (the array $a$), where $0 <= a_i <= 10^(18)$ for $1 <= i <= N$.\n\nYou should output one line containing one non-negative integer: the bitwise XOR sum of the values of all subsequences.\n\nThe value of subsequence:\n\n $[ 2 ]$ is $2 \" \"upright(O R) \" \"2 = 2$\n\n $[ 2, 1 ]$ is $2 \" \"upright(O R) \" \"1 = 3$\n\n $[ 2, 1, 5 ]$ is $5 \" \"upright(O R) \" \"1 = 5$\n\n $[ 2, 1, 5, 7 ]$ is $7 \" \"upright(O R) \" \"1 = 7$\n\n $[ 1 ]$ is $1 \" \"upright(O R) \" \"1 = 1$\n\n $[ 1, 5 ]$ is $5 \" \"upright(O R) \" \"1 = 5$\n\n $[ 1, 5, 7 ]$ is $7 \" \"upright(O R) \" \"1 = 7$\n\n $[ 5 ]$ is $5 \" \"upright(O R) \" \"5 = 5$\n\n $[ 5, 7 ]$ is $7 \" \"upright(O R) \" \"5 = 7$\n\n $[ 7 ]$ is $7 \" \"upright(O R) \" \"7 = 7$ \n\n And the XOR sum of these values is $5$.\n\n"},{"iden":"input","content":"The first line of the input will contain the number $N$ ($1 <= N <= 10^6$), representing the size of the given sequence $a$.  The following line will contain $N$ pairwise _distinct_ non-negative integers (the array $a$), where $0 <= a_i <= 10^(18)$ for $1 <= i <= N$."},{"iden":"output","content":"You should output one line containing one non-negative integer: the bitwise XOR sum of the values of all subsequences."},{"iden":"note","content":"The value of subsequence: $[ 2 ]$ is $2 \" \"upright(O R) \" \"2 = 2$ $[ 2, 1 ]$ is $2 \" \"upright(O R) \" \"1 = 3$ $[ 2, 1, 5 ]$ is $5 \" \"upright(O R) \" \"1 = 5$ $[ 2, 1, 5, 7 ]$ is $7 \" \"upright(O R) \" \"1 = 7$ $[ 1 ]$ is $1 \" \"upright(O R) \" \"1 = 1$ $[ 1, 5 ]$ is $5 \" \"upright(O R) \" \"1 = 5$ $[ 1, 5, 7 ]$ is $7 \" \"upright(O R) \" \"1 = 7$ $[ 5 ]$ is $5 \" \"upright(O R) \" \"5 = 5$ $[ 5, 7 ]$ is $7 \" \"upright(O R) \" \"5 = 7$ $[ 7 ]$ is $7 \" \"upright(O R) \" \"7 = 7$  And the XOR sum of these values is $5$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ t \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ X = (x_1, x_2, \\dots, x_n) $ be a strictly increasing sequence of distinct integers with $ x_1 < x_2 < \\dots < x_n $, and $ x_i \\in [-10^9, 10^9] $.  \nYour position starts at $ 0 $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200000 $  \n2. $ 0 \\leq t \\leq 10^9 $  \n3. $ x_1 < x_2 < \\dots < x_n $  \n\n**Objective**  \nFind the maximum number $ k \\in \\{0, 1, \\dots, n\\} $ such that there exists a subset of $ k $ bonuses at positions $ \\{x_{i_1}, x_{i_2}, \\dots, x_{i_k}\\} $ with $ i_1 < i_2 < \\dots < i_k $, and a path starting at $ 0 $, visiting these positions in order, with total travel time $ \\leq t $, where travel time between positions $ a $ and $ b $ is $ |a - b| $.\n\nEquivalently, maximize $ k $ such that there exist indices $ l \\leq r $ with $ r - l + 1 = k $, and the minimal time to collect all bonuses in $ \\{x_l, x_{l+1}, \\dots, x_r\\} $ is $ \\leq t $, where the minimal time for interval $ [l, r] $ is:  \n$$\n\\min\\left( 2 \\cdot |x_l| + |x_r - x_l|,\\ 2 \\cdot |x_r| + |x_r - x_l| \\right)\n$$  \nif $ x_l \\leq 0 \\leq x_r $, or  \n$$\n\\min\\left( |x_l| + |x_r| \\right) \\quad \\text{if both } x_l, x_r \\leq 0 \\text{ or both } \\geq 0\n$$  \nMore precisely, for a contiguous segment $ [l, r] $:  \n- If $ x_r \\leq 0 $: time = $ |x_l| $  \n- If $ x_l \\geq 0 $: time = $ x_r $  \n- If $ x_l < 0 < x_r $: time = $ 2 \\cdot \\min(|x_l|, x_r) + (x_r - x_l) $\n\nThus, define for each contiguous subarray $ [l, r] $:  \n$$\nT(l, r) = \n\\begin{cases}\n|x_l| & \\text{if } x_r \\leq 0 \\\\\nx_r & \\text{if } x_l \\geq 0 \\\\\n2 \\cdot \\min(|x_l|, x_r) + (x_r - x_l) & \\text{if } x_l < 0 < x_r\n\\end{cases}\n$$  \nMaximize $ r - l + 1 $ subject to $ T(l, r) \\leq t $.","simple_statement":"You start at position 0. There are n bonuses at distinct positions on a line, sorted in increasing order. You can move 1 unit per second. What’s the maximum number of bonuses you can collect in t seconds?","has_page_source":false}