e-olymp
Yarışlar

2013 Петрозаводск, День 6, Август 29, Задачи А - С

Байт-компьютер

Задана последовательность из n целых чисел x1, x2, ..., xn из множества {-1, 0, 1}. Байт-компьютер - это устройство, которое позволяет выполнять над последовательностью следующую операцию: можно увеличить xi+1 на xi для любого 1i < n. Не существует ограничений на диапазон целых чисел, которые может хранить байт-компьютер, то есть каждое xi может принимать произвольно малое или большое значение.

Запрограммируйте байтовый компьютер так, чтобы он преобразовывал входную последовательность в неубывающую последовательность (то есть такую, чтобы x1x2 ≤ ...≤ xn) за наименьшее количество операций.

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

Первая строка содержит число n (1n106) - количество элементов во входной последовательности байт-компьютера. Вторая строка содержит n целых чисел x1, x2, ..., xn (xi из множества {-1, 0, 1}) - входную последовательность.

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

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

Пояснение

При помощи трех операций можно получить последовательность -1, -1, -1, -1, 0, 1.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
6
-1 1 0 -1 0 1
Çıxış verilənləri #1
3
Mənbə 2013 Петрозаводск, День 6, Август 29, Задача B