Problem: A lighthouse keeper Peter commands an army of n battle lemmings. He ordered his army to stand in a line and numbered the lemmings from 1 to n from left to right. Some of the lemmings hold shields. Each lemming cannot hold more than one shield.

The more protected Peter's army is, the better. To calculate the protection of the army, he finds the number of protected pairs of lemmings, that is such pairs that both lemmings in the pair don't hold a shield, but there is a lemming with a shield between them.

Now it's time to prepare for defence and increase the protection of the army. To do this, Peter can give orders. He chooses a lemming with a shield and gives him one of the two orders: 

  * give the shield to the left neighbor if it exists and doesn't have a shield; 
  * give the shield to the right neighbor if it exists and doesn't have a shield. 



In one second Peter can give exactly one order.

It's not clear how much time Peter has before the defence. So he decided to determine the maximal value of army protection for each k from 0 to \frac{n(n-1)}2, if he gives no more that k orders. Help Peter to calculate it!

Input

First line contains a single integer n (1 ≤ n ≤ 80), the number of lemmings in Peter's army.

Second line contains n integers a_i (0 ≤ a_i ≤ 1). If a_i = 1, then the i-th lemming has a shield, otherwise a_i = 0.

Output

Print \frac{n(n-1)}2 + 1 numbers, the greatest possible protection after no more than 0, 1, ..., \frac{n(n-1)}2 orders.

Examples

Input


5
1 0 0 0 1


Output


0 2 3 3 3 3 3 3 3 3 3 


Input


12
0 0 0 0 1 1 1 1 0 1 1 0


Output


9 12 13 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 

Note

Consider the first example.

The protection is initially equal to zero, because for each pair of lemmings without shields there is no lemmings with shield.

In one second Peter can order the first lemming give his shield to the right neighbor. In this case, the protection is two, as there are two protected pairs of lemmings, (1, 3) and (1, 4).

In two seconds Peter can act in the following way. First, he orders the fifth lemming to give a shield to the left neighbor. Then, he orders the first lemming to give a shield to the right neighbor. In this case Peter has three protected pairs of lemmings — (1, 3), (1, 5) and (3, 5).

You can make sure that it's impossible to give orders in such a way that the protection becomes greater than three.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
 public class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= 998244353;
    long fac[]= new long[3000];
    public  void solve() throws IOException 
    {
      
          int n = readInt();
          ArrayList<Integer> arr = new ArrayList<>();
          int count=0;
          int glo =0;
          for(int i =0;i<n;i++)
          {
               int a= readInt();
               if(a==0)
               {
                count++;
                glo++;
               }
               else
               {
                arr.add(count);
                count=0;
               }

          }
          

          arr.add(count);

          int sum[]=new int[arr.size()];
          sum[0]=arr.get(0);

          for(int i =1;i<arr.size();i++)
            sum[i]= sum[i-1]+arr.get(i);

          int k = n;
          n = arr.size();
          int gre = k*(k-1)/2;
          int dp[][][] = new int [n+1][glo+1][10000];
          int max =(glo*glo);
          max++;
          for(int i =0;i<=n;i++)
          {
            for(int j=0;j<=glo;j++)
            {
                for(int l =0;l<=gre;l++)
                {
                   dp[i][j][l]=max;
                }
            }
          }


          
          dp[0][0][0]=0;
        
          for(int i =1;i<=n;i++)
          {
            for(int j =0;j<=glo;j++)
            {
                for(int l =0;l<=gre;l++)
                {
                    if(dp[i-1][j][l]==max)
                        continue;
                    for(int c =j;c<=glo;c++)
                    {
                         int c1 = c-j;
                         int val = arr.get(i-1);
                         dp[i][c][l+Math.abs(c-sum[i-1])]= Math.min(dp[i][c][l+Math.abs(sum[i-1]-c)],dp[i-1][j][l]+(c1)*(c1));
                    }
                }
            }
          }

          int min= glo*glo;
          
          for(int i =0;i<=gre;i++)
          {
            min=Math.min(dp[n][glo][i],min);

            int value = glo*glo;

            value = value -min;
            value = value/2;

            out.print(value+" ");

          }



      
           
      

    }
   
    
    public int value (int seg[], int left , int right ,int index, int l, int r)
    {
            
            if(left>right)
            {
              return -100000000;
            }
            if(right<l||left>r)
                return -100000000;
            if(left>=l&&right<=r)
                return seg[index];
            int mid = left+(right-left)/2;
            int val = value(seg,left,mid,2*index+1,l,r);
            int val2 = value(seg,mid+1,right,2*index+2,l,r);
            return Math.max(val,val2);

    }
   
    public int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int val ;
    int color;
    
    edge(int u, int v)
    {
       this.val=u;
       this.color=v;
    }
    public int compareTo(edge e)
    {
        return this.val-e.val;
    }
}