На доске записаны целые числа \(1, 2, 3, \dots n\) (то есть все целые числа от \(1\) до \(n\) по одному разу). Вы можете за одну операцию стереть с доски два любых числа \(a\) и \(b\) и вместо них записать новое число, равное \(\frac{a + b}{2}\) округленному вверх.
Вы должны выполнить ровно \(n - 1\) описанную операцию, при этом число, которое будет записано на доске в ходе последней операции, должно быть минимально возможным.
Например, если \(n = 4\), то следующая последовательность действий является оптимальной:
- выбрать \(a = 4\) и \(b = 2\), тогда вы запишете \(3\), и на доске останутся числа \([1, 3, 3]\);
- выбрать \(a = 3\) и \(b = 3\), тогда вы запишете \(3\), и на доске останутся числа \([1, 3]\);
- выбрать \(a = 1\) и \(b = 3\), тогда вы запишете \(2\), и на доске останется \([2]\).
Легко показать, что после \(n - 1\) операции на доске будет записано всего одно число, его и нужно минимизировать.
Выходные данные
В первую строку каждого набора входных данных выведите минимальное число, которое может остаться на доске после \(n - 1\) операции. В каждой из следующих \(n - 1\) строк выведите по два целых числа — числа \(a\) и \(b\), которые должны быть стерты с доски во время очередной операции.