eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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

Giriş verilənləri

Первая строка содержит число n (1n10^6) - количество элементов во входной последовательности байт-компьютера. Вторая строка содержит n целых чисел x[1], x[2], ..., x[n] (x[i] из множества {-1, 0, 1}) - входную последовательность.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
6
-1 1 0 -1 0 1
Çıxış verilənləri #1
3

Qeyd

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

Mənbə 2013 Петрозаводск, День 6, Август 29, Задача B