Pussycat Sonya has an array A consisting of N integers. She can replace some adjacent elements A_i and A_i+1 by their sum. Sonya can perform this operation any number of times she wants. What is the maximal number of elements with the same value Sonya can get and what are the values it could be?

Input:
The first line of input contains one integer N - the number of elements in array A.
The second line contains N space separated positive integers - elements of array A.

Output:
In the first line print the maximal number of elements with the same value Sonya can get.
In the second line print all the values it could be in ascending order separated by a space.

Constraints:
1 ≤ N ≤ 100
1 ≤ A_i ≤ 1000

---

Sample Input

(Plaintext Link)

6
11 5 6 2 8 10

Sample Output

(Plaintext Link)

2
8 10 11 16

Explanation

In this case the maximal number of elements with the same value Sonya can get is 2. Now let's see which values it could be.
That's how we can get array with two 8s:

• {11, 5, 6, 2, 8, 10} => {11, 5, 8, 8, 10}

That's how we can get array with two 10s:

• {11, 5, 6, 2, 8, 10} => {11, 5, 6, 10, 10}

That's how we can get array with two 11s:

• {11, 5, 6, 2, 8, 10} => {11, 11, 2, 8, 10}

That's how we can get array with two 16s:

• {11, 5, 6, 2, 8, 10} => {11, 5, 8, 8, 10}
• {11, 5, 8, 8, 10} => {11, 5, 16, 10}
• {11, 5, 16, 10} => {16, 16, 10}

editorial

Let us start with an example suppose the array is 

 6 2 6 2 6  

Now on a normal basis we can see that there are n*(n+1)/2 possible distinct sums.

The possible ways of forming 8 are 

(6+2), (6+2),6

6,(2+6),(2+6)

To avoid repeating of states in the considerations we go for a DP approach 

The state of the DP is dp[i][SUM]  which denotes the number of ways to obtain the SUM 

by consider i as the endpoint of the segment .

Now it is easy to realise the DP state as dp[j][sum]=1+dp[i-1][sum] where we are presently considering the 

segment from i to j.

This can be done for all i fomr 1 to n 

and j from i to n.

Lastly we copy the values of the generated sum to the pesent index if is not calulated 

             if(dp[i][s]==0)

            dp[i][s]=dp[i-1][s]

            else

             // leave it as it is computed

Now we iterate to get the largest found values

And then we iterate to get the largest values.

          ********* code goes here   ********

#include<bits/stdc++.h>

using namespace std;

int dp[110][1000010];

int arr[110];

int main()

{

int n;

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&arr[i]);

}

for(int i=1;i<=n;i++)

{

 int sum=0;

for(int j=i;j<=n;j++)

{

 sum+=arr[j];

 dp[j][sum]=1+dp[i-1][sum];

}

for(int t=1;t<=1000000;t++)

{

  if(dp[i][t]==0)

  {

    dp[i][t]=dp[i-1][t];

}

}

}

int m=-1;

        for(int i=1;i<=1000000;i++)

        {

         if(dp[n][i]>m)

         {

               m=dp[n][i];

 }

}

vector<int> ans;

for(int i=1;i<=1000000;i++)

        {

         if(dp[n][i]==m)

         {

             ans.push_back(i);

 }

}

int l=ans.size();

cout<<m<<endl;

for(int i=0;i<ans.size();i++)

cout<<ans[i]<<" ";

cout<<endl;

return 0;

}