Задача: Минимальное максимальное

Алексей Юрьевич и Михаил Леонидович отправились на поезде в Троицк. По дороге к ним подсели вахтовик и дембель. После знакомства и небольших историй о себе вахтовик и дембель решили устроить Алексею Юрьевичу и Михаилу Леонидовичу тест «на мужика»: нужно решить непростую задачку по программированию.
Помогите Алексею Юрьевичу и Михаилу Леонидовичу пройти тест «на мужика».
Задан массив целых чисел a₁,a₂,...,a_n.
Стоимостью подотрезка массива 1 <= l <= r <= n назовем величину f(l,r) = sum(l,r) − xor(l,r), где sum(l,r) = a_l +a_l+1+...+a_r, а xor(l,r) = a_l ⊕a_l+1 ⊕...⊕a_r (⊕ здесь обозначает операцию XOR, побитовое исключающее «ИЛИ» чисел, подробнее в разделе «Замечание»).
Требуется найти подотрезок заданного массива с максимальным значением f(l,r). Если ответов несколько, то среди них нужно найти подотрезок с минимальной длиной, то есть минимальным значением r − l +1.
Входные данные
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число t (1 <= t <= 10⁴) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит единственное целое число n (1 <= n <= 10⁵) — длину массива.
Вторая строка каждого набора входных данных содержит n целых чисел a₁,a₂,...,a_n (0 <= a_i <= 10⁹) — элементы массива.
Гарантируется, что сумма n по всем наборам входных данных не превосходит 2 · 10⁵.
Выходные данные
Для каждого набора входных данных выведите два числа 1 <= l <= r <= n таких, что значение f(l,r) максимально по всем подотрезкам массива a, а длина r −l +1 минимальна. Если существует несколько правильных ответов, выведите любой из них.
 

Примеры

№	Входные данные	Выходные данные
1	6 1 0 2 5 10 3 0 2 4 4 0 12 8 3 5 21 32 32 32 10 7 0 1 0 1 0 1 0	1 1 2 2 3 3 2 3 3 4 4 6

Замечание
Операция XOR двух чисел a и b — это битовая операция, которая применяется независимо к каждой паре соответствующих битов a и b. Эта операция представляет собой сложение по модулю 2. Вот её таблица истинности для пары битов:

a	b	a⊕b
0	0	0
0	1	1
1	0	1
1	1	0

В первом наборе входных данных f(1,1) = 1 − 1 = 0.
Во    втором    наборе    входных    данных    f(2,2)    =    10 − 10    =    0.    Заметим,    что f(1,2) = (10 + 5) − (10 ⊕ 5) = 0, но нам среди максимальных значений f(l,r) нужно найти подотрезок с минимальной длиной.
В четвертом наборе входных данных f(2,3) = (12+8) − (12 ⊕ 8) = 16.
В пятом наборе входных данных есть два правильных ответа, так как f(2,3) = f(3,4) и их длины равны.

 

           

Ваш ответ: