← 返回题目列表

Codeforces · 383/A

A. 挤奶奶牛

中文机器翻译题面 查看原题

Iahub 在农场帮助他的祖父。今天他必须给奶牛挤奶。有n头牛坐成一排,从左到右编号为1到n。每头牛要么面向左侧,要么面向右侧。当 Iahub 给一头奶牛挤奶时,所有看到当前奶牛的奶牛都会感到害怕,并损失一个单位的牛奶量。面向左的奶牛会看到所有指数低于其指数的奶牛,而面向右的奶牛会看到所有指数高于其指数的奶牛。一头受过惊吓的奶牛可能会再次受惊(并失去一单位的牛奶)。挤过一次奶的奶牛不会因为害怕而失去更多的牛奶。您可以假设一头奶牛永远不会失去她所能提供的所有牛奶(一头奶牛提供无限量的牛奶)。

Iahub 可以决定给奶牛挤奶的顺序。但他必须为每头奶牛挤奶一次。 Iahub 希望损失尽可能少的乳汁。打印损失的最少牛奶量。

输入

第一行包含一个整数 n (1 ≤ n ≤ 200000)。第二行包含n个整数a1,a2,...,an,其中如果牛号i朝左,则ai为0,如果朝右,则ai为1。

输出

打印一个整数,即最小的牛奶流失量。

请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

4
0 0 1 0

输出 #1

1

输入 #2

5
1 0 1 0 1

输出 #2

3

注意

在第一个样本中,Iahub 按以下顺序挤奶:奶牛 3、奶牛 4、奶牛 2、奶牛 1。当他给奶牛 3 挤奶时,奶牛 4 损失了 1 个单位的牛奶。此后,不再流失奶水。