Дан массив \(a\), состоящий из \(n\) целых чисел. Найдите отрезок значений \([x, y]\) (\(x \le y\)) и разбейте \(a\) на ровно \(k\) (\(1 \le k \le n\)) подмассивов таких, что:
- Каждый подмассив состоит из нескольких последовательных элементов \(a\), то есть он равен \(a_l, a_{l+1}, \ldots, a_r\) для некоторых \(l\) и \(r\) (\(1 \leq l \leq r \leq n\)).
- Каждый элемент \(a\) принадлежит ровно одному подмассиву.
- Для каждого подмассива количество элементов внутри отрезка \([x, y]\) (включительно) строго больше, чем количество элементов вне этого отрезка. Элемент с индексом \(i\) находится внутри отрезка \([x, y]\), если и только если \(x \le a_i \le y\).
Напечатайте любое решение, минимизирующее \(y - x\).
Выходные данные
Для каждого набора входных данных выведите \(k+1\) строк.
В первой строке выведите \(x\) и \(y\) — границы найденного отрезка.
Затем выведите \(k\) строк: \(i\)-я строка должна содержать \(l_i\) и \(r_i\) (\(1\leq l_i \leq r_i \leq n\)) — границы \(i\)-го подмассива.
Вы можете выводить подмассивы в любом порядке.
Примечание
В первом наборе входных данных должен быть только один подмассив, который обязан совпадать со всем массивом. Внутри отрезка \([1, 2]\) содержится \(2\) элемента, а вне его – \(0\). Если выбрать отрезок \([1, 1]\), то внутри него будет содержаться \(1\) элемент (\(a_1\)), вне его будет содержаться \(1\) элемент (\(a_2\)), и ответ будет некорректным.
Во втором наборе можно выбрать отрезок \([2, 2]\) и разбить массив на подмассивы \((1, 3)\) и \((4, 4)\). В подмассиве \((1, 3)\) \(2\) элемента содержатся внутри отрезка (\(a_2\) и \(a_3\)) и \(1\) элемент вне его (\(a_1\)). В подмассиве \((4, 4)\) содержится \(1\) элемент (\(a_4\)), лежащий внутри отрезка.
В третьем наборе можно выбрать отрезок \([5, 5]\) и разбить массив на подмассивы \((1, 4)\), \((5, 7)\) и \((8, 11)\). В подмассиве \((1, 4)\) содержится \(3\) элемента, лежащих внутри отрезка, и \(1\) элемент, лежащий вне его. В подмассиве \((5, 7)\) содержится \(2\) элемента, лежащих внутри отрезка, и \(1\) элемент, лежащий вне его. В подмассиве \((8, 11)\) содержится \(3\) элемента, лежащих внутри отрезка, и \(1\) элемент, лежащий вне его.