Префиксные суммы(минимумы, ...)

Подводная лодка легла на грунт на мелководье. Для её обнаружения используются данные спутника, который с высокой точностью измеряет отклонение высоты поверхности воды от среднего уровня моря. Снимок, получаемый со спутника, представляет собой массив из \(h\) строк по \(w\) элементов в каждой строке.

Введём на снимке систему координат с осью абсцисс, направленной вдоль строк снимка слева направо, и осью ординат, направленной вдоль столбцов снимка снизу вверх. Потенциальное изображение подводной лодки представляет собой любое множество элементов массива, состоящее из следующих частей:

Поскольку подводная лодка находится вблизи поверхности в районе с сильным течением, уровень воды над ней немного повышается. Поэтому изображением подводной лодки на снимке будем считать потенциальное изображение с максимально возможной суммой входящих в него элементов массива.

Требуется написать программу, которая находит на снимке изображение подводной лодки и выводит сумму его элементов.

Входные данные
Для сжатия передаваемых со спутника данных каждый элемент снимка кодируется строчной буквой английского алфавита. Первая строка входных данных содержит число \(k\) — количество использованных для кодирования букв (\(k \le 26\)). Вторая строка входных данных содержит \(k\) целых чисел \(c_i\) — значения отклонений соответствующих каждому кодовому символу по порядку букв в английском алфавите от 1 до \(k\)-й.

Третья строка входных данных содержит числа \(h\) и \(w\) — размеры снимка. Последующие \(h\) строк содержат по \(w\) символов — кодовые значения элементов снимка.

Выходные данные
Выходные данные должны содержать единственное целое число — сумму элементов массива, соответствющих изображению подводной лодки.

 

Примеры

...........
...b.......
...b....b..
.bbbbbbbbb.
........b..
...........

			 

.....
.c...
.cc..
..c..
.....

			 

.b...
.c...
.b.b.
cccbb
...b.

			 

.....
..aa.
.....
.....
.....

			 

Для примера ниже приведены несколько потенциальных изображений подводной лодки.

Ниже приведены несколько множеств элементов снимка, которые не являются потенциальными изображениями подводной лодки:

Вадим работает в ЖКХ и сегодня он крайне озабочен вопросов сосулек. А именно он наблюдает за домом по адресу — проспект Программистов, дом 404. В доме \(n\) этажей, на каждом этаже по \(m\) окон, включая первый. Окна на каждом этаже пронумерованы слева направо от \(1\) до \(m\). \(i\)-e окно \(j\)-го этажа находится ровно под \(i\)-м окном \(j + 1\)-го этажа. Под некоторыми окнами свисают сосульки.

Вадим руководит установкой на дом козырька, который будет установлен ниже первого этажа и проходить под \(d\) окнами. То есть, если начало козырька находится под окном с номером \(i\), то он проходит под всеми окнами с номерами от \(i\) до \(i + d - 1\). Вадим хочет выбрать такую позицию для козырька, чтобы над ним находилось наименьшее возможное количество сосулек и из всех подходящих вариантов выбрать такой, что начало козырька будет находиться как можно левее.

Помогите Вадиму выбрать нужное окно.

Формат входных данных
В первой строке содержатся числа \(n\), \(m\), \(d\), \(k\) — количество этажей, количество окон на каждом этаже, длина козырька и количество окон, под которыми есть сосульки, соответственно (\(1 \le n, m \le 100\),\(1 \le d \le m\), \(0 \le k \le n \cdot m\)).

В следующих \(k\) строках заданы тройки чисел \(x\), \(y\), \(z\) — номер этажа, номер окна на этаже и количество сосулек под ним (\(1 \le x \le n\), \(1 \le y \le m\), \(1 \le z \le 10\)).

Гарантируется, что каждая пара \(x\), \(y\) встречается не более одного раза.

Формат входных данных
В единственной строке выведите одно число — номер окна, под которым следует разместить начало козырька.

В первом примере длина козырька равна количеству окон на этаже, поэтому существует всего одна позиция, куда его можно поставить.

Во втором примере козырек имеет длину один и если его поставить под окнами с номерами \(1\), \(2\) или \(3\), над ним будет соответственно \(1\), \(0\) или \(2\) сосульки.

В третьем примере возможны две позиции для козырька, но так как под окнами с \(1\)-м и \(3\)-м номерами одинаковое число сосулек, а окна с номерами \(2\) будут над козырьком в любом случае, выбираем наиболее левый вариант расположения.

Вадим работает в ЖКХ и сегодня он крайне озабочен вопросов сосулек. А именно он наблюдает за домом по адресу — проспект Программистов, дом 404. В доме \(n\) этажей, на каждом этаже по \(m\) окон, включая первый. Окна на каждом этаже пронумерованы слева направо от \(1\) до \(m\). \(i\)-e окно \(j\)-го этажа находится ровно под \(i\)-м окном \(j + 1\)-го этажа. Под некоторыми окнами свисают сосульки.

Вадим руководит установкой на дом козырька, который будет установлен ниже первого этажа и проходить под \(d\) окнами. То есть, если начало козырька находится под окном с номером \(i\), то он проходит под всеми окнами с номерами от \(i\) до \(i + d - 1\). Вадим хочет выбрать такую позицию для козырька, чтобы над ним находилось наибольшее возможное количество сосулек и из всех подходящих вариантов выбрать такой, что начало козырька будет находиться как можно левее.

Помогите Вадиму выбрать нужное окно.

Формат входных данных
В первой строке содержатся числа \(n\), \(m\), \(d\), \(k\) — количество этажей, количество окон на каждом этаже, длина козырька и количество окон, под которыми есть сосульки, соответственно (\(1 \le n, m \le 100\),\(1 \le d \le m\), \(0 \le k \le n \cdot m\)).

В следующих \(k\) строках заданы тройки чисел \(x\), \(y\), \(z\) — номер этажа, номер окна на этаже и количество сосулек под ним (\(1 \le x \le n\), \(1 \le y \le m\), \(1 \le z \le 10\)).

Гарантируется, что каждая пара \(x\), \(y\) встречается не более одного раза.

Формат выходных данных
В единственной строке выведите одно число — номер окна, под которым следует разместить начало козырька.

В первом примере длина козырька равна количеству окон на этаже, поэтому существует всего одна позиция, куда его можно поставить.

Во втором примере козырек имеет длину один и если его поставить под окнами с номерами \(1\), \(2\) или \(3\), над ним будет соответственно \(0\), \(1\) или \(1\) сосулька. Таким образом подходит две позиции начала козырька, выбираем более левую.

В третьем примере возможны две позиции для козырька, но так как под окнами с \(1\)-м, в отличии от окон \(3\)-м номером, нет сосулек, а окна с номерами \(2\) будут над козырьком в любом случае, существует единственный оптимальный вариант разместить козырек.

Бизнесмен Василий готовится к уплате налогов за квартал (три месяца). Действующая налоговая система в государстве, в котором Василий ведет свой бизнес, устроена таким образом, что величина налога зависит от прибыли в конце каждого месяца. Чистая прибыль бизнесмена определяется как разница между доходом и расходом. Разумеется, если бизнес идет не очень удачно, прибыль бизнесмена может быть отрицательной —в этом случае речь идет об убытке.

Все доходы и расходы Василий записывал в журнал в виде целых чисел. Теперь Василий должен подать налоговую декларацию с суммой доходов на конец каждого месяца, другими словами ему необходимо поделить последовательность записей в журнале на три непустые части.

При этом Василий хочет сделать это таким образом, чтобы прибыль в каждой части была одинаковой (возможно даже отрицательной) — в этом случае сумма налога будет минимальной. Менять порядок записей в журнале нельзя.

По имеющимся данным определите количество способов выполнить такое разбиение.

Входные данные

В первой строке входных данных содержится единственное целое число N — количество записей в журнале Василия (3 ≤ N ≤ 10⁵).

В следующих N строках записаны целые числа a_i, соответствующие записям в журнале (−10⁸ ≤ a_i ≤ 10⁸).

Выходные данные

Программа должна вывести единственное целое число — количество способов выполнить необходимое разбиение.

Примеры

Компания <<Flatland Dynamics>> разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из \(n\) специальных платформ, пронумерованных от \(1\) до \(n\). Расстояние между \(i\)-й и \(i+1\)-й платформой равно \(d_i\), аналогично расстояние между \(n\)-й и \(1\)-й платформой равно \(d_n\).

Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью — целым числом \(a\). Робот может перепрыгнуть с платформы \(i\) на платформу \(i+1\), если \(a \ge d_i\). Аналогично, прыжок с \(n\)-й платформы на \(1\)-ю возможен, если \(a \ge d_n\). При этом после каждого прыжка ловкость робота увеличивается на \(1\).

Разработчики робота выбирают одну из платформ в качестве стартовой. Они считают эксперимент удачным, если робот может, совершив \(n\) прыжков от текущей платформы к следующей, завершить полный круг и вернуться на ту же платформу. Разработчикам необходимо выяснить, для какого минимального значения начальной ловкости робота им удастся провести эксперимент и с какой платформы роботу следует начать прыжки.

Формат входных данных
На первой строке ввода находится число \(n\) (\(3 \le n \le 10^7\)).

Вторая строка содержит одно целое число \(f\), которое описывает формат, в котором задан массив расстояний между платформами.

Если \(f = 1\), то на третьей строке находятся \(n\) целых чисел \(d_1, d_2, \ldots, d_n\) (\(1 \le d_i \le 10^{9}\)).

Если \(f = 2\), то на третьей строке находится число \(m\) \(\left(2 \le m \le \min(n, 10^5)\right)\) и три целых числа \(x\), \(y\) и \(z\) (\(0 \le x, y, z \le 10^9\)). На четвертой строке находятся \(m\) целых чисел \(c_1, c_2, \ldots, c_m\) (\(1 \le c_i \le 10^9\)). Значения \(d_i\) вычисляются по следующим формулам.

Если \(1 \le i \le m\), то \(d_i = c_i\).

Если \(m + 1 \le i \le n\), то \(d_i = \left((x\cdot d_{i-2} + y\cdot d_{i-1} + z)\bmod 10^9\right) + 1\).

Здесь \(\bmod\) означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом <<%>>.

Формат выходных данных
Требуется вывести два целых числа: минимальную допустимую начальную ловкость \(a\) и номер стартовой платформы, на которую можно разместить робота, чтобы успешно провести эксперимент.

Если возможных стартовых платформ для минимальной начальной ловкости несколько, можно вывести любую из них.

Замечание
Во втором примере массив расстояний между платформами равен \([1, 2, 3, 4, 5, 18, 45, 112, 273, 662]\). Значения от \(d_6\) до \(d_{10}\) вычисляются по формулам:

\(d_6 = \left((1\cdot d_4+2\cdot d_5 + 3) \bmod 10^9\right)+1 = \left((1\cdot 4+2\cdot 5+3)\bmod 10^9\right)+1=18\)

\(d_7 = \left((1\cdot d_5+2\cdot d_6 + 3) \bmod 10^9\right)+1 = \left((1\cdot 5+2\cdot 18+3)\bmod 10^9\right)+1=45\)

\(d_8 = \left((1\cdot d_6+2\cdot d_7 + 3) \bmod 10^9\right)+1 = \left((1\cdot 18+2\cdot 45+3)\bmod 10^9\right)+1=112\)

\(d_9 = \left((1\cdot d_7+2\cdot d_8 + 3) \bmod 10^9\right)+1 = \left((1\cdot 45+2\cdot 112+3)\bmod 10^9\right)+1=273\)

\(d_{10} = \left((1\cdot d_8+2\cdot d_9 + 3) \bmod 10^9\right)+1 = \left((1\cdot 112+2\cdot 273+3)\bmod 10^9\right)+1=662\)

Друзья Вася Л. и Петя П. — талантливые мальчики, которые любят писать песни собственного сочинения. В будущем они хотят стать популярными музыкантами. Ребята знают: чтобы добиться успеха, нужно регулярно тренироваться. Именно поэтому они каждый день пишут по новой песне, совершенствуя свое мастерство.

Однажды Петя в очередной раз написал грустную песню про любовь и поспешил показать ее Васе. Песня представляет собой строку из маленьких букв английского алфавита. У Васи сразу возникло \(q\) вопросов про эту песню. Каждый вопрос представляет собой некоторый отрезок песни с позиции \(l\) до позиции \(r\) включительно. Вася рассматривает подстроку, образованную символами на этом отрезке, а затем повторяет каждую букву в этой подстроке \(k\) раз, где \(k\) — порядковый номер соответствующей буквы в алфавите. Например, если Вася выбрал подстроку <<abbcb>>, то он повторит букву <<a>> один раз, каждую из букв <<b>> — по два раза, букву <<c>> — три раза, и полученная строка будет равна <<abbbbcccbb>>, ее длина равна 10. Вася интересуется именно длиной полученной строки.

Помогите Пете ответить Васе на его вопросы, а именно, для каждого из заданных вопросов определите длину строки, которую выпишет Вася.

Формат входных данных
В первой строке вводятся числа \(n, q\) (\(1\leq n\leq 100\,000, 1\leq q \leq 100\,000\)) — длина песни и количество вопросов.

Во второй строке дана строка \(s\) — сама песня, представляющая собой строку длины \(n\) из маленьких букв английского алфавита.

В следующих \(q\) строках даны описания вопросов. Каждое описание состоит из двух чисел \(l\) и \(r\) \((1 \leq l \leq r \leq n)\) — границы каждого из вопросов.

Формат выходных данных
Выведите \(q\) строк — для каждого вопроса выведите длину строки, которую выпишет Вася.

В первом примере Васю интересуют три вопроса. В первом вопросе Вася рассматривает подстроку <<aba>>, которая превратится в <<abba>>, а значит, ответ на этот вопрос равен 4. Во втором вопросе Вася рассматривает подстроку <<baca>>, которая превратится в <<bbaccca>>, а значит, ответ на этот вопрос будет равен 7. В третьем вопросе Вася рассматривает всю строку <<abacaba>>, которая превратится в <<abbacccabba>> — строку длины 11.

Для получение номера буквы можно использовать следующий код:

• В языке python3 или pypy3 выражение ord(x) - 96, например ord(a) - 96 равно 1, а ord(x) - 96 равно 24.

• В языке c++ выражение x - 96, например a - 96 равно 1, а x - 96 равно 24.

• В языке pascal выражение ord(x) - 96, например ord(a) - 96 равно 1, а ord(x) - 96 равно 24.

Петя открыл цветочный магазин. Магазин Пети занимается изготовлением и продажей букетов. Всего существует \(n\) видов цветов, занумерованных от 1 до \(n\). Каждый букет, чтобы быть гармоничным и красивым, должен состоять из цветов всех видов, по одной штуке каждого вида. В магазине уже есть \(a_i\) штук цветов вида \(i\). На цветочной базе можно купить цветок любого вида за 1 рубль.

Определите, сколько букетов сможет собрать Петя, если потратит не более \(x\) рублей на покупку цветов на базе. Ответьте на \(q\) запросов с различными \(x_i\).

Формат входных данных
В первой строке входных данных находятся два целых числа \(n\) и \(q\) (\(1 \le n, q \le 10^5\)) — количество различных типов цветов и количество запросов.

Во второй строке находятся \(n\) целых чисел \(a_1, a_2, \cdots, a_n\) (\(0 \le a_i \le 10^9\)) — количество цветов каждого вида, имеющихся в магазине.

В третьей строке находятся \(q\) целых чисел \(x_1, x_2, \cdots, x_q\) (\(0 \le x_i \le 10^9\)) — запросы Пети.

Формат выходных данных
Выходной файл должен содержать \(q\) чисел, где \(i\)-е число это максимальное количество букетов, которое можно собрать потратив не более \(x_i\) рублей.

Примечание
В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа.

В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет.

Во втором запросе у него есть 2 рубля, он не может сделать два букета за 2 рубля, поэтому ответ по прежнему 1.

В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.

Физрук формирует дистанцию для забега школьников на уроке. Согласно требованиям, длина дистанции должна быть от \(L\) до \(R\) метров.

Дистанция пройдет вдоль дорожки в парке около школы. Вдоль дорожки растет \(n\) деревьев, первое дерево находится на расстоянии \(d_1\) метров от начала дорожки, \(i\)-е дерево находится на расстоянии \(d_i\) метров от предыдущего дерева для \(i > 1\). Для удобства физрук хочет, чтобы дистанция начиналась либо в начале дорожки, либо около какого-либо дерева, и заканчивалась также около какого-либо дерева.

Если подходящих вариантов организовать дистанцию несколько, физрук хочет выбрать из них тот, в котором финиш находится как можно ближе к началу дорожки. Если подходящих вариантов все еще несколько, он хочет выбрать тот, где старт находится как можно ближе к началу дорожки.

Помогите физруку выбрать точки начала и конца дистанции.

Формат входных данных
Первая строка ввода содержат два целых числа \(L\) и \(R\) (\(1 \le L \le R \le 3 \cdot 10^{14}\)). Обратите внимание, что для считывания \(L\) и \(R\) необходимо хотя бы 64-битный тип данных (<<long long>> в C++).

Вторая строка ввода содержит целое число \(n\) (\(1 \le n \le 300\,000\)).

Третья строка ввода содержит \(n\) целых чисел \(d_1, d_2, \ldots, d_n\) (\(1 \le d_i \le 10^9\)).

Формат выходных данных
Выведите два целых числа: \(s\) и \(t\) — расстояние от начала дорожки до начала и конца дистанции, соответственно. Должны выполняться условия: \(0 \le s < t\), \(L \le t - s \le R\), \(s = 0\) или \(s\) совпадает с позицией некоторого дерева, \(t\) совпадает с позицией некоторого дерева.

Если выбрать организовать дистанцию не получится, выведите \(s = -1\), \(t = -1\).

left = "0" и right = "11101", сумма = 1 + 4 = 5 
left = "01" и right = "1101", сумма = 1 + 3 = 4 
left = "011" и right = "101", сумма = 1 + 2 = 3 
left = "0111" и right = "01", сумма = 1 + 1 = 2 
left = "01110" и right = "1", сумма = 2 + 1 = 3

Битовый баланс равен максимальному значению суммы, следовательно ответ 5.

Назовем опорным числом последовательности натуральных чисел - целое число x, такое что:

• Сумма всех элементов между 1 и x включительно равна сумме всех элементов между x и n включительно.

Например, для числовой последовательности из 8 элементов (числа от 1 до 8 включительно) опорным числом будет число 6 (1+2+3+4+5+6 = 6+7+8).

Для заданного натурального числа n, найдите минимальную опорную точку последовательности натуральных чисел от 1 до n.

Формат входных данных
Программа получает на вход натуральное число n (1 <= n <= 2000).

Формат выходных данных
Выведите минимальную опорную точку последовательности натуральных чисел от 1 до n. Если такой точки не существует, вернуть -1.

На уроке информатики маленькая девочка Алёна осваивает редактирование таблиц в одной очень известной программе.

Сейчас у неё есть таблица из целых чисел, состоящая из \(n\) строк и \(m\) столбцов. Через \(a_{i,j}\) будем обозначать число в \(i\)-й строке и \(j\)-м столбце. Будем говорить, что таблица отсортирована по неубыванию по \(j\)-му столбцу, если \(a_{i, j} \leq a_{i + 1, j}\) для всех \(i\) от \(1\) до \(n - 1\).

Учительница дала Алёне \(k\) заданий. Для каждого из заданий известны два числа \(l\) и \(r\) и требуется ответить на вопрос: если от таблицы оставить только строки с \(l\) по \(r\) включительно, то будет ли она отсортирована по неубыванию хотя бы по одному столбцу? Другими словами, существует ли такое \(j\), что \(a_{i, j} \leq a_{i + 1, j}\) для всех \(i\) от \(l\) до \(r - 1\) включительно.

Алёна ещё слишком маленькая, чтобы справиться с заданием самостоятельно — помогите ей!

Формат входных данных
В первой строке входных данных записаны два целых положительных числа \(n\) и \(m\) (\(1 \leq n \cdot m \leq 100\,000\)) — количество строк и столбцов в таблице соответственно. Обратите внимание, что дано ограничение только на произведение этих чисел, то есть на количество элементов таблицы.

В каждой из следующих \(n\) строк записаны \(m\) целых чисел, \(j\)-e число в \(i\)-й из этих строк соответствует значению \(a_{i, j}\) (\(1 \leq a_{i, j} \leq 10^9\)).

В следующей строке входных данных задано число \(k\) (\(1 \leq k \leq 100\,000\)) — количество заданий учительницы, которые нужно выполнить Алёне.

В \(i\)-й из последующих \(k\) строк числа \(l_i\) и \(r_i\) (\(1 \leq l_i \leq r_i \leq n\)).

Формат выходных данных
В \(i\)-й строке выведите “Yes”, если в таблице, полученной из исходной оставлением строк с \(l_i\) по \(r_i\) включительно будет столбец, по которому она отсортирована по неубыванию, и “No” в противном случае.

В приведенном примере таблица не отсортирована ни по одному столбцу, но, например, строки 1–3 отсортированы по столбцу 1, а строки 4–5 по столбцу 3. В данной задаче 100 тестов, помимо тестов из условия, каждый из них оценивается в 1 балл. Результаты работы ваших решений на первых 60 тестах будут доступны во время соревнования. Результаты работы на остальных 40 будут доступны после окончания соревнования.

Решения, корректно работающие при \(1 \leq n, k \leq 100\) и \(m = 1\), наберут не менее 10 баллов.

Решения, корректно работающие при \(1 \leq n, m, k \leq 100\), наберут не менее 40 баллов.

Дан массив целых чисел nums (первый элемент массива имеет индекс 0). Найдите наименьший "средний" индекс массива.

Средний индекс - это индекс, для которого выполняется условие: сумма элементов слева от индекса равна сумме элементов справа от индекса (не включая сам элемент со средним индексом). То есть

leftSum[middle] = rightSum[middle].

Где:

middle - средний индекс массива.
leftSum[middle] - сумма элементов, стоящих слева от элемента nums[middle]. Если таких элементов нет, то leftSum[middle] = 0. 
rightSum[middle] - сумма элементов, стоящих справа от элемента nums[middle]. Если таких элементов нет, то rightSum[middle] = 0.

Формат входных данных
Первая строка содержит натуральное число N (1 <= N <= 105) - количество элементов в массиве nums. Вторая строка содержит N чисел numsi - элементы массива nums (|numsi|<=1000, 0 <= i < N).

Формат выходных данных
Выведите одно число - наименьший "средний" индекс массива. Если такого индекса нет, то выведите -1.

Задан массив натуральных чисел \(A = [a_1, a_2, \ldots, a_n]\). Отрезком массива \(A\) с \(l\) по \(r\) будем называть массив \([a_l, a_{l+1}, \ldots, a_r]\).

Для заданного массива \(A\) и числа \(k\) требуется найти количество пар \((l, r)\), таких что \(l \le r\) и сумма чисел на отрезке массива \(A\) с \(l\) по \(r\) делится на \(k\) без остатка.

На первой строке ввода заданы целые числа \(n\) "— число элементов массива \(A\) и \(k\) (\(1 \le n \le 200\,000\), \(2 \le k \le 10^9\)).

На второй строке заданы целые числа \(a_1, a_2, \ldots, a_n\) — элементы массива \(A\) (\(1 \le a_i \le 10^9\)).

Выведите одно число: количество пар \((l, r)\), таких что \(l \le r\), и сумма чисел на отрезке массива \(A\) с \(l\) по \(r\) делится на \(k\) без остатка.

В примере подходят следующие отрезки:

• \(l = 1\), \(r = 3\), отрезок \([1, 2, 3]\)

• \(l = 1\), \(r = 4\), отрезок \([1, 2, 3, 4]\)

• \(l = 2\), \(r = 2\), отрезок \([2]\)

• \(l = 2\), \(r = 5\), отрезок \([2, 3, 4, 5]\)

• \(l = 3\), \(r = 5\), отрезок \([3, 4, 5]\)

• \(l = 4\), \(r = 4\), отрезок \([4]\)

Дан массив целых чисел (nums) с индексацией, начинающейся с 0. Сформируйте новый массив целых чисел (ans), в котором i-й элемент вычисляется по формуле:

 ans[i] = |leftSum[i] - rightSum[i]|.

Где:

leftSum[i] - сумма элементов, стоящих слева от элемента nums[i]. Если таких элементов нет, то leftSum[i] = 0.
rightSum[i] - сумма элементов, стоящих справа от элемента nums[i]. Если таких элементов нет, то rightSum[i] = 0.

Выведите элементы нового массива на экран в одну строку, разделяя элементы одним пробелом. Количество элементов нового массива должно быть равно количеству элементов исходного.

Формат входных данных
Первая строка содержит число n (n <= 10⁵). Во второй строке записаны n целых чисел numsi - элементы массива nums (|numsi| < 10⁶).

Формат выходных данных
Выведите на экран n чисел - элементы нового массива на экран в одну строку, разделяя элементы одним пробелом.

Примеры