There are n armchairs, numbered from 1 to n from left to right. Some armchairs are occupied by people (at most one person per armchair), others are not. The number of occupied armchairs is not greater than n/2.

For some reason, you would like to tell people to move from their armchairs to some other ones. If the i-th armchair is occupied by someone and the j-th armchair is not, you can tell the person sitting in the i-th armchair to move to the j-th armchair. The time it takes a person to move from the i-th armchair to the j-th one is |i - j| minutes. You may perform this operation any number of times, but these operations must be done sequentially, i. e. you cannot tell a person to move until the person you asked to move in the last operation has finished moving to their destination armchair.

You want to achieve the following situation: every seat that was initially occupied must be free. What is the minimum time you need to do it?

Input

The first line contains one integer n (2 ≤ n ≤ 5000) — the number of armchairs.

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 1). a_i = 1 means that the i-th armchair is initially occupied, a_i = 0 means that it is initially free. The number of occupied armchairs is at most n/2.

Output

Print one integer — the minimum number of minutes you have to spend to achieve the following situation: every seat that was initially occupied must be free.

Examples

Input


7
1 0 0 1 0 0 1


Output


3


Input


6
1 1 1 0 0 0


Output


9


Input


5
0 0 0 0 0


Output


0

Note

In the first test, you can perform the following sequence:

  1. ask a person to move from armchair 1 to armchair 2, it takes 1 minute; 
  2. ask a person to move from armchair 7 to armchair 6, it takes 1 minute; 
  3. ask a person to move from armchair 4 to armchair 5, it takes 1 minute. 



In the second test, you can perform the following sequence:

  1. ask a person to move from armchair 1 to armchair 4, it takes 3 minutes; 
  2. ask a person to move from armchair 2 to armchair 6, it takes 4 minutes; 
  3. ask a person to move from armchair 4 to armchair 5, it takes 1 minute; 
  4. ask a person to move from armchair 3 to armchair 4, it takes 1 minute. 



In the third test, no seat is occupied so your goal is achieved instantly.
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

const int N = 5e3 + 10,M = N * N;

int n,S,T,a[N];
vector<int>v;

int head[N],cur[N],to[M],last[M],c[M],w[M],cnt = 1;
void add(int a,int b,int c1,int d){
    to[++cnt] = b;
    c[cnt] = c1;
    w[cnt] = d;
    last[cnt] = head[a];
    head[a] = cnt;
    to[++cnt] = a;
    c[cnt] = 0;
    w[cnt] = -d;
    last[cnt] = head[b];
    head[b] = cnt;
}

int dist[N],flag[N];
bool spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[S] = 0;
    queue<int>q;
    q.push(S);
    cur[S] = head[S];
    while(q.size()){
        int p = q.front();
        q.pop();
        flag[p] = 0;
        for(int i = head[p]; i != -1; i = last[i]){
            int j = to[i];
            if(dist[j] > dist[p] + w[i] && c[i]){
                dist[j] = dist[p] + w[i];
                cur[j] = head[j];
                if(!flag[j]){
                    flag[j] = 1;
                    q.push(j);
                }
            }
        }
    }
    if(dist[T] != 0x3f3f3f3f) return true;
    return false;
}

int vis[N];
int dfs(int x,int sum){
    if(x == T) return sum;
    int used = 0;
    vis[x] = 1;
    for(int i = cur[x]; i != -1; i = last[i]){
        int j = to[i];
        cur[x] = i;
        if(!vis[j] && dist[j] == dist[x] + w[i] && c[i]){
            int dd = dfs(j,min(sum - used,c[i]));
            used += dd;
            c[i] -= dd;
            c[i ^ 1] += dd;
        }
    }
    vis[x] = 0;
    if(used == 0) dist[x] = -1;
    return used;
}

int dinic(){
    int sum = 0;
    while(spfa()){
        int d = dfs(S,0x3f3f3f3f);
        sum += d * dist[T];
    }
    return sum;
}

int main(){
    cin >> n;
    memset(head,-1,sizeof head);
    S = 0; T = n + 1;

    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        if(a[i] == 1) add(S,i,1,0);
        else add(i,T,1,0);
        if(i - 1 >= 1) add(i,i - 1,0x3f3f3f3f,1);
        if(i + 1 <= n) add(i,i + 1,0x3f3f3f3f,1);
    }

    cout << dinic() << endl;

    return 0;
}