Нина дала вам массив целых чисел \(a_1, a_2, \ldots, a_n\) длины \(n\).
Вы можете выполнить следующую операцию не более \(5\cdot 10^5\) раз (возможно, ноль):
- Выбрать два целых числа \(l\) и \(r\) таких, что \(1 \le l \le r \le n\), вычислить \(x\) как \(\operatorname{MEX}(\{a_l, a_{l+1}, \ldots, a_r\})\), и одновременно присвоить \(a_l:=x, a_{l+1}:=x, \ldots, a_r:=x\).
Здесь \(\operatorname{MEX}\) множества целых чисел \(\{c_1, c_2, \ldots, c_k\}\) определяется как наименьшее неотрицательное целое число \(m\), которое не встречается в множестве \(c\).
Ваша цель — максимизировать сумму элементов массива \(a\). Найдите максимальную сумму и постройте последовательность операций, которая достигает этой суммы. Обратите внимание, что вам не нужно минимизировать количество операций в этой последовательности, вам лишь нужно использовать не более \(5\cdot 10^5\) операций в вашем решении.
Выходные данные
В первой строке выведите два целых числа \(s\) и \(m\) (\(0\le m\le 5\cdot 10^5\)) — максимальную сумму элементов массива \(a\) и количество операций в вашем решении.
В \(i\)-й из следующих \(m\) строк выведите два целых числа \(l\) и \(r\) (\(1 \le l \le r \le n\)), представляющие параметры \(i\)-й операции.
Можно показать, что максимальная сумма элементов массива \(a\) всегда может быть получена не более чем за \(5 \cdot 10^5\) операций.
Примечание
В первом примере, после операции с \(l=1\) и \(r=2\) массив \(a\) становится равным \([2,2]\). Можно показать, что невозможно достичь большей суммы элементов \(a\), поэтому ответ \(4\).
Во втором примере, начальная сумма элементов равна \(13\), а достичь большей суммы невозможно.
В третьем примере массив \(a\) изменяется следующим образом:
- после первой операции (\(l=3\), \(r=3\)), массив \(a\) становится равным \([1,100,0,1]\);
- после второй операции (\(l=3\), \(r=4\)), массив \(a\) становится равным \([1,100,2,2]\).
Можно показать, что большей суммы элементов \(a\) достичь невозможно, поэтому ответ \(105\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
0 1
|
4 1
1 2
|
|
2
|
3
1 3 9
|
13 0
|
|
3
|
4
1 100 2 1
|
105 2
3 3
3 4
|
|
4
|
1
0
|
1 1
1 1
|