Информатика

Сад Беси имеет \(N\) растений, помеченных от \(1\) до \(N\) (\(2\leq N\leq 5\cdot 10^5\)) слева направо. Беси знает, что растение \(i\) требует не менее \(w_i\) (\(0\leq w_i \leq 10^6\)) единиц воды.

У Беси своеобразная ирригационная система с \(N-1\) каналами, пронумерованными от \(1\) до \(N-1\). Каждый канал \(i\) имеет ассоциированную с ним стоимость \(c_i\) (\(1\le c_i\le 10^6\)), такую что Беси может заплатить \(c_i*k\) чтобы обеспечить растение \(i\) и \(i+1\) каждое \(k\) единицами воды где \(k\) неотрицательное целое число.

Беси сильно занята и может не иметь времени использовать все каналы. Для каждого \(2\leq i \leq N\) вычислите минимальную стоимость требуемую, чтобы доставить воду растениям от \(1\) до \(i\) используя только первые \(i-1\) каналов.

**Замечание: Время на тест в этой задаче 4 сек, в 2 раза больше, чем по умолчанию.**

Беси использует свой изящный телескоп чтобы сделать фотографии всех звёзд на ночном небе. Её телескоп может сделать фото \(N \times N\) (\(1 \leq N \leq 1000\)) пикселов, где каждый пиксел это или звезда, или пустое небо. Каждая звезда будет представлена ровно одним пикселом, и никакие две звезды на разделяют один и тот же пиксел.

Ночью происходит что-то странное со звёздами на небе. Каждая звезда или исчезает или перемещается на \(A\) пикселов вправо и на \(B\) пикселов вниз (\(0 \leq A,B \leq N\)). Если звезда исчезает или перемещается за границу фото, она больше не появляется на втором фото.

Беси делает фотографии до и после перемещений, но после экспериментов, она случайно наложила одну фотографию на другую. Теперь она видит белые пикселы, которые были пустыми на обеих фотографиях, серые пикселы, где звезда была ровно на одном фото и чёрные пикселы, где была звезда на обоих фотографиях. Беси также помнит, что на второй фотографии не появились новые звёзды, поэтому первая фотография содержит все звёзды ночного неба. Если не существует исходного положения звёзд, которое может произвести финальное фото, выведите \(-1\).

**Замечание: Время на тест в этой задаче 4 сек, в 2 раза больше, чем по умолчанию.**

Беси использует свой изящный телескоп чтобы сделать фотографии всех звёзд на ночном небе. Её телескоп может сделать фото \(N \times N\) (\(1 \leq N \leq 1000\)) пикселов, где каждый пиксел это или звезда, или пустое небо. Каждая звезда будет представлена ровно одним пикселом, и никакие две звезды на разделяют один и тот же пиксел.

Ночью происходит что-то странное со звёздами на небе. Каждая звезда или исчезает или перемещается на \(A\) пикселов вправо и на \(B\) пикселов вниз (\(0 \leq A,B \leq N\)). Если звезда исчезает или перемещается за границу фото, она больше не появляется на втором фото.

Беси делает фотографии до и после перемещений, но после экспериментов, она случайно наложила одну фотографию на другую. Теперь она видит белые пикселы, которые были пустыми на обеих фотографиях, серые пикселы, где звезда была ровно на одном фото и чёрные пикселы, где была звезда на обоих фотографиях. Беси также помнит, что на второй фотографии не появились новые звёзды, поэтому первая фотография содержит все звёзды ночного неба. Если не существует исходного положения звёзд, которое может произвести финальное фото, выведите \(-1\).

Беси помогает Эльзе играть со словами. Слова берутся из банка, содержащего \(M\) различных слов, ни одно слово не является префиксом другого.

Пока банк не пустой, Беси выбирает слово из банка, удаляет его из банка, читает его Эльзе по одному символу за раз слева направо. Задача Эльзы сказать Беси, как только она уникально определит слово, после чего Беси прекращает чтение.

Беси уже решила читать слова из словаря в порядке \(w_1,w_2,\dots,w_M\). Если Эльза ответит так быстро, как это возможно, сколько символов из каждого слова прочитает Беси?

Слова заданы в сжатом формате. Сначала мы определяем \(N+1\) (\(1\le N\le 10^6\)) различных слов и затем банк слов состоит из всех этих слов, ни одно из которых не является префиксом другого. Слова определяются следующим образом:

• Изначально, 0-ое слово - пустая строка.
• Затем для каждого each \(1\le i\le N\), \(i\)-ое слово будет равно \(p_i\)-ому слову плюс дополнительный символ в конце (\(0\le p_i<i\)). Символы выбираются так, что все \(N+1\) слов различны.

Беси стоит пере двумя стогами сена. Первый содержит \(a\) снопов, второй - \(b\) снопов \(1\le a,b\le 10^{18}\)).

Она должна превратить их в стоги с \(c\) и \(d\) снопами - ни больше, ни меньше.

Беси может выполнять только такие два заклинания:

• Увеличить размер первого стога РЅР° количество СЃРЅРѕРїРѕРІ РІРѕ втором стоге.
• Увеличить размер второго стога РЅР° количество СЃРЅРѕРїРѕРІ РІ первом стоге.

Для каждого из \(T\) (\(1\le T\le 10^4\)) независимых подтестов, выведите минимальное количество операций, чтобы добиться нужного результата, или если это невозможно, выведите -1.

ПР�МЕР ВВОДА:

4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3

ПР�МЕР ВЫВОДА:

-1
3
-1
0

В первом подтесте невозможно, посокльку изначально \(b>d\), разрешённые операции могут только увеличивать \(b\).

Во втором подтесте изначально стоги имеют \((5, 3)\) снопов. Беси может увеличить первый стог на количество снопов во втором получит \((8, 3)\). Затем увеличит количество второй стог на новое количество снопов в первом, получит \((8, 11)\) Затем сделает эту операцию ещё раз и получит \((8, 19)\) � это минимальное количество операций, чтобы получить данный результат.

Заметим, что в третьем подтесте ответ не такой как во втором, потому, что \(c\) и \(d\) поменяны местами (порядок куч имеет значение).

В четвертом подтесте не требуется выполнять операции.

ПР�МЕР ВВОДА:

1
1 1 1 1000000000000000000

ПР�МЕР ВЫВОДА:

999999999999999999

Автор: Benjamin Qi

Фермер Джон выстроил \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) своих коров в ряд \(a\). \(i\)'-ая корова от начала ряда \(a\) помечена целым числом \(a_i\) (\(1 \leq a_i \leq N\)). Несколько коров могут быть помечены одним и тем же числом.

ФД конструирует ряд \(b\) следующим образом:

• Изначально массив \(b\) пустой.
• Пока массив \(a\) не пустой, удалить первый элемент ряда \(a\) и добавить или не добавить этот элемент в конец массива \(b\).

ФД хочет сконструировать \(b\) так, чтобы последовательность меток в \(b\) от начала к концу была лексикографически наибольшей.

Прежде чем ФД начнёт конструировать ряд \(b\), он может выполнить следующую операцию не более чем один раз.

• Выбрать корову в ряду \(a\) и переместить её в любую позицию, кроме текущей.

При условии, что ФД оптимально выполняет эту операцию не более одного раза, выведите лексикографически наибольшую последовательность \(b\), которую он сможет получить.

Каждый тест состоит из \(T\) (\(1 \leq T \leq 100\)) независимых подтестов.

**Замечание: Время на тест для этой задачи 3сек, в 1.5 большее чем по умолчанию. Память на тест для этой задачи 512MB, в два раза больше чем по умолчанию.**

Беси проходит тест вида да/нет из \(N\) вопросов (\(1\le N\le 2\cdot 10^5\)). За \(i\)-ый вопрос она может добавить \(a_i\) баллов если ответит правильно, и отнять \(b_i\) баллов, если ответит неправильно или не изменить сумму, если не ответит вообще на вопрос (\(0<a_i,b_i\le 10^9\)).

Беси знает ответы на все вопросы, но боится, что администратор теста Эльза подменит до \(k\) вопросов так, чтоб получилось, что Беси ответила неправильно.

Заданы \(Q\) (\(1\le Q\le N+1\)) кандидатов величин \(k\) (\(0\le k\le N\)), определите количество баллов, которые Беси гарантированы для каждого \(k\), зная, что она должна ответить не менее чем на \(k\) вопросов.

Ответьте на \(Q\) (\(1\le Q\le 10^5\)) независимых запроса следующего вида:

Вам даны четыре целых числа \(a,b,c,d\) (\(-10^{18}\le a,b,c,d\le 10^{18}\)). За одну операцию Вы можете сделать либо \(a\mathrel{+}=b\), или \(b\mathrel{+}=a\) Определите минимальное количество операций чтобы трансформировать \((a,b)\) в \((c,d)\), если это невозможно сделать, выведите \(-1\).

У Фермера Джона есть двоичная строка длиной \(N\) \((1 \leq N \leq 10^9)\), изначально из одних нулей.

Сначала он выполнит \(M\) (\(1 \leq M \leq 2 \cdot 10^5\)) изменений строки по порядку. Каждое изменение переворачивает каждый символ от \(l\) до \(r\). То есть \(0\) изменяется на \(1\) и наоборот.

Затем он задаёт Вам \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) вопросов. Для каждого вопроса Вы должны ввести лексикографически наибольшую подпоследовательность длины \(k\) состоящую из символов подстроки от \(l\) до \(r\). Если Ваш ответ - двоичная строка \(s_1s_2 \dots s_k\), выведите \(\sum_{i=0}^{k-1} 2^i \cdot s_{k-i}\) (то есть строка интерпретируется как двоичное число) по модулю \(10^9+7\).

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

Напомним, что строка \(A\) лексикографически больше чем строка \(B\) такой же длины если и только если в первой позиции \(i\), если она существует, \(A_i \neq B_i\), выполняется \(A_i > B_i\).

ПР�МЕР ВВОДА:

5 3 9
1 5
2 4
3 3
1 5 5
1 5 4
1 5 3
1 5 2
1 5 1
2 5 4
2 5 3
2 5 2
2 5 1

ПР�МЕР ВЫВОДА:

21
13
7
3
1
5
5
3
1

После выполнения \(M\) операций, строка такова: \(10101\).

Для первого запроса - длины \(5\) ответ вся строка \(10101\), которая интерпретируется как \(1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 21\).

Для второго запроса, существует \(5\) уникальных подпоследовательностей длины \(4\): \(0101\), \(1101\), \(1001\), \(1011\), \(1010\). Лексикографически наибольшая из них \(1101\), которая интерпретируется как \(1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0 = 13\).

Для третьей строки лексикографически наибольшая последовательность \(111\), которая интерпретируется как \(7\).

ПР�МЕР ВВОДА:

9 1 1
7 9
1 8 8

ПР�МЕР ВЫВОДА:

3

ПР�МЕР ВВОДА:

30 1 1
1 30
1 30 30

ПР�МЕР ВЫВОДА:

73741816

Не забудьте выводить ответ по модулю \(10^9+7\).

Автор: Chongtian Ma

У Фермера Джона есть \(N\) коров, помеченных числами от \(1\) до \(N\) (\(2\le N\le 16\)). Отношение дружбы между этими коровами может быть смоделировано ненаправленным графом с \(M\) (\(0\le M\le N(N-1)/2\)) ребрами. Две коровы являются друзьями, если и только если между ними есть ребро в этом графе.

За одну операцию Вы можете добавить или удалить одно ребро в этом графе. Посчитайте минимальное количество операций, которое требуется выполнить, чтобы обеспечить следующее свойство в этом графе: Если коровы \(a\) и \(b\) - друзья, тогда для любой другой коровы \(c\) по крайней мере одна из коров \(a\) и \(b\) является другом коровы \(c\).

У Фермера Джона есть квадратный холст, представленный решёткой из \(N\) * \(N\) ячеек, (\(2 \leq N \leq 2000\), \(N\) чётное). Он рисует по следующим правилам:

1. Сначала он делит холст на четыре равных квадранта, разделённых горизонтальными и вертикальными линиями через центр холста.
2. Далее он рисует любимую картинку в правом верхнем квадранте холста. Каждая ячейка верхнего правого квадранта или закрашена (представлено символом '#') или не закрашена (представлено символом '.').
3. Наконец, гордясь своим рисунком, он отражает его через ранее указанные вертикальные и горизонтальные линии в другие квадранты холста.

Например, предположим \(N=8\) и ФД нарисовал следующую картинку в правом верхнем квадранте на шаге 2:

.#..
.#..
.##.
....

Тогда после отображения через горизонтальные и вертикальные линии в другие квадранты на шаге 3, холст будет выглядеть так:

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

Однако, пока ФД спал, Беси пробралась в его амбар и украла холст. А затем занялась вандализмом: Она стерла некоторые ячейки и закрасила некоторые другие ячейки. После чего вернула холст ФД.

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

Вам задан холст после вандализма Беси, а также последовательность \(U\) (\(0\le U \leq 10^5\)) модификаций холста, каждое переключает ячейку в '.', если в ней была '#' и наоборот. Прежде каждого обновления и после каждого обновления выведите минимальное количество операций \(x\), которое требуется выполнить, чтобы отражение было удовлетворено.

ПР�МЕР ВВОДА:

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

ПР�МЕР ВЫВОДА:

4
3
2
1
0
1

Следующий холст удовлетворяет условию отражения и отличается от оригинального холста на 4 операции:

....
####
####
....

Невозможно сделать исходный холст удовлетворяющим условию отражения испольуя менее чем 4 операции.

После обновления \((1, 3)\), холст выглядит так:

....
##.#
####
..##

Требуется 3 операции, чтобы холст стал удовлетворять условию отражения.

После обновления \((2, 3)\), холст выглядит так:

....
####
####
..##

Требуется 2 операции, чтобы сделать холст удовлетворяющим условию отражения.

Автор: Chongtian Ma

Беси учиться кодировать на простом языке программирования. Она сначала написала корректную программу, а затем выполнила её, получив некоторую выходную последовательность.

Определение:

• программа это непустая последовательность операторов.
• Оператор имеет форму "PRINT \(c\)" где \(c\) - целое число, или "REP \(o\)", за которым следует программа, за которой следует "END", где \(o\) - целое число не менее 1.

• Выполнение программы исполняет операторы последовательности.
• Выполнение оператора "PRINT \(c\)" добавляет \(c\) в выходную последовательность.
• Выполнение оператора, начинающегося с "REP \(o\)" выполняет внутреннюю программу \(o\) раз

Пример программы Беси.

REP 3
    PRINT 1
    REP 2
        PRINT 2
    END
END

Эта программа выведет последовательность \([1,2,2,1,2,2,1,2,2]\).

Беси хочет вывести последовательность \(N\) (\(1 \le N \le 100\)) положительных целых чисел. Эльза предложила Беси использовать не более \(K\) (\(1 \le K \le 3\)) операторов "PRINT". Заметим, что Беси может использовать сколько хочет операторов "REP". Также заметим, что каждое положительное число в последовательности не более \(K\).

Для каждого \(T\) (\(1 \le T \le 100\)) независимого подтеста определите, может ли Беси написать программу, которая выведет некоторую заданную последовательность, используя не более \(K\) операторов "PRINT".

Вам дан массив \(a\) из \(N\) неотрицательных чисел \(a_1, a_2, \dots, a_N\) (\(1\le N\le 2\cdot 10^5, 0\le a_i\le N\)). За одну операцию Вы можете изменить любой элемент \(a\) на любое неотрицательное число.

mex массива это минимальное неотрицательное число, которого нет в массиве. Для каждого \(i\) в интервале от \(0\) до \(N\) включительно, вычислите минимальное количество операций, которое Вы должны сделать, чтобы сделать mex массива \(a\) равным \(i\).

Беси ищет новую работу. К счастью сейчас \(K\) фермеров проводят интервью для найма работников. Поскольку желающих найти работу много, фермеры решили перенумеровать коров и интервьюировать их в порядке нумерации. \(N\) коров подали заявки на интервью, поэтому у Беси номер \(N+1\) (\(1 \leq K \leq N \leq 3 \cdot 10^5\)).

Процесс интервью проходит следующим образом. В момент времени \(0\) фермер \(i\) начинает интервью с коровой \(i\) для каждого \(1 \leq i \leq K\). После того, фермер заканчивает интервью он немедленно начинает интервьюировать следующую корову по порядку. Если несколько фермеров закончили интервью в одно и то же время, следующая корова может выбрать сама к какому из фермеров пойдёт на интервью.

Для каждого \(1\le i\le N\), Беси знает, что интервью коровы \(i\) займёт ровно \(t_i\) минут (\(1 \leq t_i \leq 10^9\)). Однако она не знает, какого фермера предпочтёт каждая корова.

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

Фермер Джон хочет справедливо разделить пакеты сена между его двумя любимыми коровами Беси и Эльза. У него есть \(N\) ( \(1\le N\le 2\cdot 10^5\)) пакетов сена, упорядоченных в невозрастающем порядке. Где \(i\)-ый пакет сена имеет \(a_i\) единиц сена ($2\cdot 10^5\ge a₁\ge a₂ \ge \dots \ge a_N \ge 1$).

ФД хочет разделить непрерывный отрезок пакетов \(a_l, \dots, a_r\) между Беси и Эльзой, рассматривая пакеты в порядке от \(l\) до \(r\), и когда рассматривает \(i\)-ый пакет он даёт его корове, у которой сейчас меньше сена. Если равно - даёт Беси.

Вам даётся \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов, каждый описывается тремя целыми числами \(l,r,x\) (\(1\le l\le r\le N\), \(|x|\le 10^9\)). Для каждого запроса, введите на сколько больше единиц сена будет у Беси, после обработки пакетов от \(l\) до \(r\), если Беси начнёт с количеством сена на \(x\) единиц больше чем у Эльзы. Заметим эта величина отрицательна, если вначале у Эльзы будет на \(x\) единиц больше чем у Беси.

**Замечание: Время на тест и ограничение по памяти для этой задачи 3сек и 512MB, что, соответственно, в 1.5 и 2 раза больше чем по умолчанию.**

Каждая из \(N\) (\(1 \leq N \leq 10^5\)) коров Фермера Джона имеет свой ID-номер в виде битовой строки (строки соcтоящей из символов '0' и '1'). Беси, старейшая корова, помнит ID-номера всех коров и любит спрашивать у коров их ID-номера.

Когда у коровы спрашивают ID-номер, они начинают отвечать правильную битовую строку, но могут забыть и остановиться, не закончив её. Когда Беси слышит битовую строку, если та не является ID-номером ни одной коровы на ферме, она пожимает плечами и уходит. Однако если это ID-номер другой коровы на ферме, она предполагает, что произошла кража личных данных и закрывает ферму на карантин. Заметим, что это может случиться даже если корова говорит свой полный правильный ID-номер.

ФД хочет избавиться от последней ситуации и добавить несколько битов к некоторым ID-номерам. За одну секунду он может добавить один бит в конец ID-номера любой коровы. Определите минимальное количество времени, которое потребуется чтобы избежать карантина по совпадению правильного ID-номера.

У Беси есть два массива длины \(N\) (\(1 \le N \le 500\)). \(i\)-ый элемент первого массива есть \(a_i\) (\(1 \le a_i \le 10^6\)). \(i\)-ый элемент второго массива есть \(b_i\) (\(1 \le b_i \le 10^6\)).

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

1. Каждый элемент принадлежит точно 1 подмассиву.
2. Оба массива разделены на одинаковое количество подмассивов - пусть \(k\). То есть, первый массив разделён ровно на \(k\) подмассивов. И второй массив также разделён ровно на \(k\) подмассивов.
3. Для всех \(1 \le i \le k\),, среднее \(i\)-го подмассива слева первого массива строго меньше либо равно среднему \(i\)-го подмассива слева второго массива.

Подсчитайте сколькими способами можно разделить массивы на непустые подмассивы выполнив указанные ограничения. Выводить ответ по модулю \(10^9+7\). Два способа считаются различными, если количество элементов подмассива различается или некоторый элемент принадлежит различным подмассивам.

Фермер Джон и его \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) коров на Манхеттене. Коровы сбежали и гуляют по городу. В Манхеттене \(N\) (\(1 \le N \le 2 \cdot 10^5\)) дорог проходящие бесконечно на \(x\)-\(y\)-плоскости. Все они расположены или горизонтально, или вертикально. Каждая горизонтальная или вертикальная может быть смоделирована уравнением вида \(y = c_i\) или \(x = c_i\), где \(c_i\) целое число в интервале от \(0\) до \(10^9\) включительно.

ФД знает точно где каждая корова начала путешествие и время путешествия. Каждая из коров движется по следующему шаблону:

• РћРЅР° двигается РЅР° север (\(+y\)) или восток (\(+x\)) РЅР° РѕРґРЅСѓ единицу РІ секунду.
• Если РѕРЅР° РЅР° одиночной РґРѕСЂРѕРіРµ, РѕРЅР° продолжает двигаться РїРѕ ней.
• Если РѕРЅР° РЅР° пересечении РґРІСѓС… РґРѕСЂРѕРі, РѕРЅР° идёт РЅР° север, РЅР° чётной секунде путешествия Рё РЅР° восток иначе.

ВАм дана карта Манхэттена и информация о каждой корове, помогите ФД где его коровы сейчас.

ПР�МЕР ВВОДА:

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

ПР�МЕР ВЫВОДА:

14 5
7 13
6 15
6 16
110 4

(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

Автор: Benjamin Qi

Беси прыгает вдоль числовой прямой длины \(N\) \((1 \leq N \leq 10^5)\) по позициям \(1,2,\dots,N\) слева направо. Она начинает в позиции \(S\) \((1 \leq S \leq N)\) прыжком вправо со стартовой энергией \(1\). Если энергия Беси равна \(k\), то её следующий прыжок будет на \(k\) единиц вперёд от её текущей позиции.

Каждая целочисленная позиция от \(1\) до \(N\) это или цель, или прыжковая площадка. Каждая цель или прыжковая площадка имеет целочисленную величину от \(0\) до \(N\) включительно. Прыжковая площадка со значением \(v\) увеличивает энергию Беси на \(v\) и изменяет на противоположное направление прыжков. Цель со значением \(v\) будет сломана, если на неё приземлится Беси с энергией не менее \(v\). Приземление на цель не изменяет энергию и направление Беси. Сломанная цель остаётся сломанной, но Беси может на неё прыгать, энергия и направление не меняются.

Если Беси будет прыгать бесконечное количество времени или до тех пор, пока Беси покинет этот отрезок прямой, сколько целей она сломает?

Если Беси начинает на цели, которую она может сломать, она немедленно делает это. Аналогично, если Беси начинает на прыжковой площадке, то эффект площадки применяется перед первым прыжком.

У Фермера Джона \(N\) (\(1\le N\le 2\cdot 10^5\)) участков травы на прямой, где участок \(i\) имеет уровень бактерий, который отличается на \(a_i\) от здоровой травы (\(-10^{15}\le a_i \le 10^{15}\)). Например, если \(a_i = -3\), тогда кусок \(i\) имеет уровень бактерий на 3 меньше, чем нормальный. И нужно прибавить ровно 3 дополнительных единицы бактерий, чтобы уровень бактерий в этом куске рассматривался как нормальный.

ФД хочет обеспечить, чтобы каждый кусок травы был скорректирован, чтобы получить нормальные уровни бактерий на них. У него есть два вида пестицидов, один добавляет бактерии, другой удаляет бактерии. ФД распространяет любой из двух видов пестицидов, стоя в куске \(N\) (самом правом куске) и выбирает уровень мощности \(L\) (\(1 \leq L \leq N\)).

Сила действия спрейера уменьшается по мере увеличения расстояния от него. Например, если фермер выберет пестицид, который добавляет бактерии, тогда \(L\) единиц бактерий в участок \(N\), \(L-1\) единиц бактерий в участок \(N-1\), \(L-2\) единицы бактерий в участок \(N-2\) и т.д. Участки \(1 \ldots N-L\) не получат бактерий, поскольку мощность спрейера недостаточна, чтобы их достать. Аналогично, если ФД выберет пестициды, которые удаляют бактерии, тогда \(L\) единиц бактерий будет удалено с участка \(N\), \(L-1\) единиц бактерий будет удалено с участка \(N-1\) и т.д. Опять, участки \(1 \ldots N-L\) будут не изменены.

Определите минимальное количество раз, которое ФД должен применить свой спрейер так, чтобы на каждом участке стало рекомендованное количество бактерийю Гарантируется, что ответ не превысит \(10^9\).

Может потребоваться использование 64-битного типа данных (например "long long" в C/C++)