Вам дан массив \(a\) из \(n\) неотрицательных целых чисел. Вы можете применять на нём следующую операцию.
- Выберите два индекса \(l\) и \(r\) (\(1 \le l < r \le n\)).
- Если \(a_l + a_r\) нечетно, то выполните \(a_r := a_l\). Если \(a_l + a_r\) четно, то выполните \(a_l := a_r\).
Найдите любую последовательность из не более чем \(n\) операций, которая делает массив \(a\) неубывающим. Можно доказать, что она всегда существует. Обратите внимание, что вам не нужно минимизировать количество операций.
Массив \(a_1, a_2, \ldots, a_n\) неубывающий тогда и только тогда, когда \(a_1 \le a_2 \le \ldots \le a_n\).
Выходные данные
Для каждого набора входных данных выведите в первой строке одно целое число \(m\) (\(0 \le m \le n\)) — количество операций.
Затем выведите \(m\) строк. Каждая строка должна содержать два целых числа \(l_i, r_i\), которые являются индексами, выбранными вами в \(i\)-й операции (\(1 \le l_i < r_i \le n\)).
Если решений несколько, выведите любое из них.
Примечание
Во втором примере \(a\) изменяется следующим образом:
- Выберите индексы \(3\) и \(4\). \(a_3 + a_4 = 3\) нечетно, поэтому надо выполнить \(a_4 := a_3\). После этого \(a = [1, 1000000000, 3, 3, 5]\).
- Выберите индексы \(1\) и \(2\). \(a_1 + a_2 = 1000000001\) нечетно, поэтому надо выполнить \(a_2 := a_1\). Теперь \(a = [1, 1, 3, 3, 5]\) и массив неубывающий.
В первом и третьем примерах \(a\) уже неубывающий.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
7 8
5
1 1000000000 3 0 5
1
0
|
0
2
3 4
1 2
0
|