### Problem Statement You are given an array of n integers ( 0 <= n <= 1000 ). Find a contiguous subsequence of these numbers \[ a $ _{i} $ , a $ _{j} $ \] ( 1 <= i, j <= n ), such that the Exclusive-OR of these numbers is maximum. ( That is, a $ _{i} $ XOR a $ _{i+1} $ XOR... a $ _{j} $ should be maximum ). ### Input The test case contains exactly 2 lines of input. The first line contains a single integer n ( 0 <= n <= 1000 ), the total number of integers in the sequence given to you. The next line contains n space separated integers such that the ith integer denotes a $ _{i} $ . ( 0 <= a $ _{i} $ <= 10 $ ^{9} $ ). Note that these integers need not necessarily be distinct. ### Output Output two lines. In the first line, print out the value of the maximum XOR. In the second line, print out i and j with a space separating them, such that \[ a $ _{i} $ , a $ _{j} $ \] ( both endpoints inclusive ) denotes the contiguous subsequence with the maximum XOR value. In case there is more than one subsequence with the maximum XOR value, print out the pair ( i, j ) such that ( i, j ) is lexicographically smallest. ( Formally, we say that a pair ( a, b ) is lexicographically smaller than another pair ( c,d ) if and only if (i) a < c or (ii) a=c and b < d. ) **NOTE** : The subsequence must be non-empty, but may be allowed to contain just one integer. ( i.e, in this case, i = j ) ### Example ``` Input #1: 1 4 ``` `Output #1:` ``` 4 1 1 ``` ``` Input #2: 3 1 2 3 Output #2: 3 1 2 Explanation: ``` 1. In the first test case, since there is only one number, the maximum XOR would be simply the value of that number ( in this case, 4 ), and i = j = 1. 2. In the second test case, the maximum XOR value is 3, but there are 2 contiguous subsequences that define the same XOR value - (i) \[ 1, 2 \] since 1 XOR 2 = 3 (ii) \[ 3, 3 \] since this subsequence contains just the single integer 3. But since \[ 1, 2 \] is lexicographically smaller than \[ 3, 3 \], \[ 1, 2 \] is the desired output.

SP12726 QN01 - XOR Game

Description

Input Format

Output Format