Яхуб помогает деду на ферме. Сегодня надо доить коров. Перед Яхубом выстроились в ряд n коров, пронумерованных от 1 до n слева направо. Каждая корова смотрит либо налево, либо направо. Когда Яхуб доит корову, все остальные коровы, которые это видят, пугаются и теряют одну единицу молока в вымени. Если корова смотрит налево, то она видит всех коров с номерами меньше ее номера. Если же корова смотрит направо, то она видит всех коров с номерами большее ее номера. Корова, которая напугалась однажды, может напугаться еще раз (и потерять еще одну единицу молока). Если корову уже подоили один раз, то она больше не пугается и не теряет молоко. Предполагается, что корова никогда не теряет все молоко, что у нее есть (у коровы в вымени бесконечное количество молока).
Яхуб может определить порядок, в котором он доит коров. Тем не менее он обязан подоить каждую корову ровно один раз. Яхуб хочет потерять как можно меньше молока. Выведите наименьшее количество молока, которое он может потерять.
Выходные данные
Выведите единственное целое число, минимальное количество потерянного молока.
Пожалуйста, не используйте спецификатор %lld для чтения и записи 64 битных целых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом тестовом примере Яхуб доит коров в следующем порядке: корова 3, корова 4, корова 2, корова 1. Когда он доит корову 3, корова 4 теряет 1 единицу молока. Больше молоко не теряется.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
0 0 1 0
|
1
|
|
2
|
5
1 0 1 0 1
|
3
|