Это простая версия задачи. Единственное различие состоит в том, что в этой версии \(q = 1\).
Вам дан массив целых чисел \(a_1, a_2, \ldots, a_n\).
Стоимостью подотрезка массива \([l, r]\), \(1 \leq l \leq r \leq n\), назовем величину \(f(l, r) = \operatorname{sum}(l, r) - \operatorname{xor}(l, r)\), где \(\operatorname{sum}(l, r) = a_l + a_{l+1} + \ldots + a_r\), а \(\operatorname{xor}(l, r) = a_l \oplus a_{l+1} \oplus \ldots \oplus a_r\) (\(\oplus\) обозначает побитовое исключающее ИЛИ).
У вас будет \(q = 1\) запрос. Каждый запрос задается парой чисел \(L_i\), \(R_i\), где \(1 \leq L_i \leq R_i \leq n\). Вам нужно найти подотрезок \([l, r]\), \(L_i \leq l \leq r \leq R_i\) с максимальным значением \(f(l, r)\). Если подходящих ответов несколько, то среди них нужно найти подотрезок с минимальной длиной, то есть минимальным значением \(r - l + 1\).
Выходные данные
Для каждого набора входных данных выведите \(q\) пар чисел \(L_i \leq l \leq r \leq R_i\), таких что значение \(f(l, r)\) максимально, а среди таких длина \(r - l + 1\) минимальна. Если существует несколько правильных ответов, выведите любой из них.
Примечание
В первом наборе входных данных \(f(1, 1) = 0 - 0 = 0\).
Во втором наборе входных данных \(f(1, 1) = 5 - 5 = 0\), \(f(2, 2) = 10 - 10 = 0\). Заметим, что \(f(1, 2) = (10 + 5) - (10 \oplus 5) = 0\), но нам среди максимальных значений \(f(l, r)\) нужно найти подотрезок с минимальной длиной. Поэтому правильными ответами будут только отрезки \([1, 1]\) и \([2, 2]\).
В четвертом наборе входных данных \(f(2, 3) = (12 + 8) - (12 \oplus 8) = 16\).
В пятом наборе входных данных есть два правильных ответа, так как \(f(2, 3) = f(3, 4)\) и их длины равны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 1
0
1 1
2 1
5 10
1 2
3 1
0 2 4
1 3
4 1
0 12 8 3
1 4
5 1
21 32 32 32 10
1 5
7 1
0 1 0 1 0 1 0
1 7
|
1 1
1 1
1 1
2 3
2 3
2 4
|