Tommy has a children's toy "sorter", with
n pegs arranged in a row. There is now no more than one disk on each peg (that is, there is a disk on some peg, but on some it No). Tommy wants to rearrange the given disks on the pegs so that they form a non-decreasing sequence when viewed from left to right. That is, on each next peg, the number of disks must be no less than on the previous one. What is the minimum number of Tommy's disks that need to be shifted?
Please note that some pegs may be empty at the end of sorting. Some pegs may contain more than 1 disc.
Input
The program receives as input in the first line an integer
n (1 <=
n <= 10
5), the number of peg on "sorter". The next line contains
n integers
a1,
a2, ...
an – the presence of a disc on the corresponding peg (0 <=
ai <= 1). the number
0 means that there is no disk on the
ith peg,
1 – there is a disc.
Imprint
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
8
0 0 1 1 1 1 1 1
|
0
|
| 2 |
eleven
1 1 0 0 1 0 0 1 1 1 0
|
3
|