AbdelKader enjoys math. He feels very frustrated whenever he sees an incorrect equation and so he tries to make it correct as quickly as possible!

Given an equation of the form: A₁ o A₂ o A₃ o ... o A_n  =  0, where o is either + or -. Your task is to help AbdelKader find the minimum number of changes to the operators + and -, such that the equation becomes correct.

You are allowed to replace any number of pluses with minuses, and any number of minuses with pluses.

The first line of input contains an integer N (2 ≤ N ≤ 20), the number of terms in the equation.

The second line contains N integers separated by a plus + or a minus -, each value is between 1 and 10⁸.

Values and operators are separated by a single space.

If it is impossible to make the equation correct by replacing operators, print  - 1, otherwise print the minimum number of needed changes.

7
1 + 1 - 4 - 4 - 4 - 2 - 2

3

3
5 + 3 - 7

//#include <bits/stdc++.h>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <iostream>

#include <algorithm>

#include <iostream>

#include <cstdio>

#include <string>

#include <cstring>

#include <stdio.h>

#include <queue>

#include <stack>;

#include <map>

#include <set>

#include <ctype.h>

#include <string.h>

#include <vector>

#define ME(x , y) memset(x , y , sizeof(x))

#define SF(n) scanf("%d" , &n)

#define rep(i , n) for(int i = 0 ; i < n ; i ++)

#define INF  0x3f3f3f3f

#define mod 10

#define PI acos(-1)

using namespace std;

typedef long long ll ;

int a[];

char c[];

int n ;

int min1 = INF ;

int vis[];

void dfs(int s , int l , int ans)

{

    //cout << s  << " " << l << " " << ans << endl ;

    if(l == n)

    {

        if(s == )

        {

            min1 = min(min1 , ans);

        }

        return ;

    }

    if(c[l] == '-')

    {

        dfs(s+a[l] , l+ , ans + );

        dfs(s-a[l] , l+ , ans);

    }

    if(c[l] == '+')

    {

        dfs(s+a[l] , l+ , ans);

        dfs(s-a[l] , l+ , ans+);

    }

}

int main()

{

    scanf("%d" , &n);

    scanf("%d " , &a[]);

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

    {

        cin >> c[i] >> a[i];

    }

    dfs(a[] ,  , );

    if(min1 != INF)

        cout << min1 << endl ;

    else

        cout << - << endl ;

    return ;

}