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 个单位的牛奶。此后,不再流失奶水。