Омкар стоит у подножия горы Селеста. Вершина находится в \(n\) метрах от него, и он может видеть всю гору до вершины, поэтому для каждого \(1 \leq j \leq n\) он знает, что высота горы в точке в \(j\) метрах от него равна \(h_j\). Известно, что для всех \(j\) удовлетворяющих \(1 \leq j \leq n - 1\), \(h_j < h_{j + 1}\) (то есть высоты строго возрастают).
Внезапно происходит оползень! Пока происходит оползень, происходит следующее: каждую минуту, если \(h_j + 2 \leq h_{j + 1}\), то один квадратный метр грязи будет скользить с позиции \(j + 1\) в позицию \(j\), так что \(h_{j + 1}\) уменьшается на \(1\), а \(h_j\) увеличивается на \(1\). Эти изменения происходят одновременно, так, например, если \(h_j + 2 \leq h_{j + 1}\) и \(h_{j + 1} + 2 \leq h_{j + 2}\) для какого-то \(j\), то \(h_j\) будет увеличено на \(1\), \(h_{j + 2}\) будет уменьшено на \(1\), а \(h_{j + 1}\) будет увеличено и уменьшено на \(1\), что означает, что на самом деле \(h_{j + 1}\) в течение этой минуты не изменится.
Оползень заканчивается, когда не будет такого \(j\), что \(h_j + 2 \leq h_{j + 1}\). Помогите Омкару выяснить, каковы будут значения \(h_1, \dots, h_n\) после окончания оползня. Можно доказать, что при заданных ограничениях оползень всегда заканчивается через некоторое число минут.
Обратите внимание, что из-за большого количества входных данных, рекомендуется, чтобы ваш код использовал быстрый ввод.
Примечание
Первоначально гора имеет высоты \(2, 6, 7, 8\).
В первую минуту у нас есть \(2 + 2 \leq 6\), таким образом \(2\) увеличивается до \(3\), а \(6\) уменьшается до \(5\), оставляя \(3, 5, 7, 8\).
Во вторую минуту у нас есть \(3 + 2 \leq 5\) и \(5 + 2 \leq 7\), таким образом \(3\) увеличивается до \(4\), \(5\) остается без изменений, а \(7\) уменьшается до \(6\), оставляя \(4, 5, 6, 8\).
На третьей минуте у нас есть \(6 + 2 \leq 8\), так что \(6\) увеличивается до \(7\), а \(8\) уменьшается до \(7\), оставляя \(4, 5, 7, 7\).
На четвертой минуте у нас есть \(5 + 2 \leq 7\), таким образом \(5\) увеличивается до \(6\), а \(7\) уменьшается до \(6\), оставляя \(4, 6, 6, 7\).
На пятой минуте у нас есть \(4 + 2 \leq 6\), поэтому \(4\) увеличивается до \(5\), а \(6\) уменьшается до \(5\), оставляя \(5, 5, 6, 7\).
На шестой минуте ничего больше не может измениться, поэтому оползень останавливается, и наш ответ — \(5, 5, 6, 7\).