import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        for (int k = 0; k < n; k++) {
            String s = sc.nextLine();
            // 双指针
            boolean flag = true;
            int i = 0, j = s.length() - 1;
            while(i < j){
                if (s.charAt(i) != s.charAt(j)){
                    if(isVaild(s, i, j - 1)){
                        System.out.println(j);
                        flag = false;
                        break;
                    } else if(isVaild(s, i + 1, j)){
                        System.out.println(i);
                        flag = false;
                        break;
                    }
                }
                i++;
                j--;
            }
            if (flag)
                System.out.println(-1);
        }
    }
    
    public static boolean isVaild(String s, int i, int j){
        while (i < j){
            if (s.charAt(i) != s.charAt(j))
                return false;
            i++;
            j--;
        }
        return true;
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int cnt = 0; // y cnt
        int res = 0; // res
        for (int i = s.length() - 1; i >= 0; i--){
            if (s.charAt(i) == 'y')
                cnt++;
            if (s.charAt(i) == 'x'){
                res = (res + cnt) % 1000000007;
                cnt = (cnt * 2) % 1000000007;
            }
        }
        System.out.println(res % 1000000007);
        
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] nums = new long[n];
        for (int i = 0; i < n; i++)
            nums[i] = sc.nextInt();
        long max = 0;
        long cnt = 0, deal = 0;
        for(int i = 1; i < n; i++){
            if (nums[i] > nums[i - 1]){
                max += nums[i] - nums[i - 1];
                if (deal == 0)
                    cnt++;
                deal = 1;
            }
            if (nums[i] < nums[i - 1]){
                cnt += deal;
                deal = 0;
            }
        }
        System.out.println(max + " " + cnt + deal);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[100001];
        for (int i = 0; i < n; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            nums[x]++;
            nums[y]--;
        }
        int cnt = 0;
        int res = 0;
        for (int i = 1; i < nums.length; i++){
            cnt += nums[i];
            res = Math.max(res, cnt);
        }
        System.out.println(res);
    }
}

import java.util.*; 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums = new int[k];
        for (int i = 0; i < n; i++)
            nums[(sc.nextInt()) % k]++;
        
        // 
        int sum = nums[0] > 0 ? 1 : 0;
        for (int i = 1, j = k - 1; i <= j; i++, j--){
            sum += (i == j)
                ? (nums[i] >= 1 ? 1 : 0) // 中间这个数，取一个，取多加起来会被整除的
                : Math.max(nums[i], nums[j]);
        }
        System.out.println(sum);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int W = sc.nextInt();
        int[] ws = new int[n];
        int[] vals = new int[n];
        for (int i = 0; i < n; i++){
            ws[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++){
            vals[i] = sc.nextInt();
        }
        int[] dp = new int[W + 1];
        for (int i = 1; i <= n; i++){
            int w = ws[i - 1], v = vals[i - 1];
            for (int j = W; j >=0; j--){
                if (j >= w){
                    dp[j] = Math.max(dp[j], dp[j - w] + v);
                }
            }
        }
        System.out.println(dp[W]);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += sc.nextInt() - 1;
        }
        System.out.println(sum);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = n * 2;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < m; i++)
            list.add(sc.nextInt());
        int idx = 0;
        int sum = 0;
        while (idx < list.size()){
            int lastIdx = list.lastIndexOf(list.get(idx));
            sum += (lastIdx - idx - 1);
            list.remove(lastIdx);
            idx++;
        }
        System.out.println(sum);
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            sc.nextLine();
            int[] a = new int[26];
            String s = sc.nextLine();
            for(int i = 0; i < n; i++){
                a[s.charAt(i) - 'A']++;
            }
            Arrays.sort(a);
            long sum = 0L;
            int cnt = 0;
            for (int i = a.length - 1; i >=0; i--){
                if (cnt + a[i] > m)
                    continue;
                cnt += a[i];
                sum += (long)a[i] * (long)a[i];
            }
            sum = cnt == m ? sum : sum + (m - cnt) * (m - cnt);
            System.out.println(sum);
        }
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long start = 1;
        long end = n;
        long temp = 0;
        // 二分法
        while (start < end){
            long mid = start + (end - start) / 2;
            if (minNum(mid, n)){
                temp = mid;
                end = mid;
            } else{
                start = mid + 1;
            }
        }
        System.out.println(temp);
    }
    public static boolean minNum(long m, long n){
        long nums1 = 0;
        long temp = n;
        long mid = 0;
        while (temp >= 0){
            if (temp < m){
                nums1 += temp;
                break;
            }
            nums1 += m;
            temp -= m;
            temp -= temp / 10;
        }
        mid = n % 2 == 0 ? n / 2 : (n + 1) / 2;
        return nums1 >= mid ? true : false;
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        // 任意位置翻转，形成环
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        s += s;
        int cur = 1, max = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) != s.charAt(i + 1)){
                cur++;
            } else{
                max = Math.max(max, cur);
                cur = 1;
            }
        }
        if (cur == s.length())
            System.out.println(max / 2);
        else
            System.out.println(max);
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        sc.nextInt();
        while (sc.hasNext()){
            int n = sc.nextInt();
            int k = sc.nextInt();
            int ans = 0;
            // 模拟
            if (n < 3 || k == n || k < 1)
                ans = 0;
            else {
                ans = Math.min(n - k, k - 1);
            }
            System.out.println(0 + " " + ans);
        }
    } 
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n <= 5)
            System.out.println(1);
        else {
            int cnt = 0;
            int t = 5;
            while(n != 0 && t > 0){
                int tmp = n / t;
                n = n - tmp * t;
                t--;
                cnt += tmp;
            }
            System.out.println(cnt);
        }

    }
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        ArrayList<Integer> towers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            towers.add(sc.nextInt());
        }
        int cnt = 0;
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        int max = Collections.max(towers);
        int min = Collections.min(towers);
        while (max - min > 1 && cnt < k){
            max = Collections.max(towers); min = Collections.min(towers);
            list1.add(towers.indexOf(max) + 1); list2.add(towers.indexOf(min) + 1);
            towers.set(towers.indexOf(min), min + 1);
            towers.set(towers.indexOf(max), max - 1);
            cnt++;
        }
        System.out.println(Collections.max(towers) - Collections.min(towers) + " " + cnt);
        for (int i = 0; i < list1.size(); i++) {
            System.out.println(list1.get(i) + " " + list2.get(i));
        }
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] nums1 = new int[n];
        int[] nums2 = new int[n];
        int[] sumInterest = new int[n];
        for (int i = 0; i < n; i++) {
            nums1[i] = sc.nextInt();
        }
        int sum0 = 0;
        int sum1 = 0;
        for (int i = 0; i < n; i++) {
            nums2[i] = sc.nextInt();
            if (nums2[i] == 1)
                sum0 += nums1[i];
            else
                sum1 += nums1[i];
            sumInterest[i] = sum1;
        }
        int cur = 0;
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (nums2[i] == 0){
                if (i + k - 1 <= n - 1) {
                    cur = sumInterest[i + k - 1] - (i - 1 > 0 ? sumInterest[i - 1] : 0);
                } else {
                    cur = sumInterest[n - 1] - (i - 1 > 0 ? sumInterest[i - 1] : 0);
                }
            }
            max = Math.max(cur, max);
        }
        System.out.println(max + sum0);
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        while (k-- > 0) {
            int n = sc.nextInt();
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            System.out.println(eql(nums));
        }
    }

    public static String eql(int[] arr){
        Arrays.sort(arr);
        int a = arr[0];
        int b = arr[arr.length-1];
        if(arr.length == 2){
            return "YES";
        }
        if((a+b) % 2 != 0){
            return "NO";
        }
        int mid = (a+b)/2;
        int offset = b - mid;
        for(int i = 0;i < arr.length;i++){
            if(!(arr[i] + offset == mid || arr[i] - offset == mid || arr[i] == mid)){
                return "NO";
            }
        }
        return "YES";
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = 3;
        int i = 0;
        Integer[] nums = new Integer[n];
        while (n-- > 0){
            nums[i++] = sc.nextInt();
        }
        Arrays.sort(nums, (o1, o2) -> o2 - o1);
        System.out.println((nums[0] - nums[1]) + (nums[1] - nums[2]));
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        int[] a = new int[k + 1];
        for (int i = 0; i < n; i++) {
            a[sc.nextInt()]++;
        }
        Arrays.sort(a);
        if (a[1] == 0)
            System.out.println(0);
        else
            System.out.println(a[1]);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[26];
        for (int i = 0; i < 26; i++) {
            a[i] = sc.nextInt();
        }
        sc.nextLine();
        String s = sc.nextLine();
        int cnt = 1;
        int tmp = 100;
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i) - 'a';
            int w = a[c];
            sum += w;
            if (sum >= tmp){
                sum = sum == tmp ? 0 : w;
                cnt++;
            }
        }
        System.out.println(cnt + " " + sum);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = 0, b = 0, c = 0, d = 0;
        int[] nums = new int[4];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = sc.nextInt();
        }
        a = (nums[0] + nums[2]) / 2;
        b = (nums[1] + nums[3]) / 2;
        c = nums[3] - b;
        if (b - c != nums[1])
            System.out.println("No");
        else if (a - b != nums[0])
            System.out.println("No");
        else if (a + b != nums[2])
            System.out.println("No");
        else
            System.out.println(a + " " + b + " " + c);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n % 8 == 0)
            System.out.println(n / 8);
        else {
            int t = n / 8;
            if (t == 0 && n % 6 == 0)
                System.out.println(n / 6);
            else {
                n -= (t - 1) * 8;
                if (n % 6 == 0)
                    System.out.println(t - 1 + (n / 6));
                else
                    System.out.println(-1);
            }
        }
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();

        System.out.println(reverse(reverse(x) + reverse(y)));
    }

    public static int reverse(int x) {
        int res = 0;
        while (x != 0){
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        long[] dp = new long[x + 1];
        dp[1] = 3;
        dp[2] = 9;
        for (int i = 3; i <= x; i++) {
            dp[i] = 2 * dp[i - 1] + dp[i - 2]; // 把状态方程给忘了...可惜了
        }
        System.out.println(dp[x]);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int x = (int) Math.sqrt(num);
        int l = 0, r = x;
        int sum = 0;
        while (l < r) {
            if (l == 0 && r * r == num){
                sum += 4;
                l++;
                r--;
            }
            else if ((l * l + r * r) == num) {
                sum += 8;
                l++;
                r--;
            }
            else if ((l * l + r * r) < num)
                l++;
            else
                r--;
        }
        if (l == r && l * l + r * r == num)
            System.out.println(sum += 4);
        else
            System.out.println(sum);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int l = 0, r = n - 1;
        int cnt = 0;
        while (l < r){
            if (a[l] == a[r]){
                l++;
                r--;
            } else if (a[l] < a[r]){
                a[l + 1] = a[l] + a[l + 1];
                l++;
                cnt++;
            } else {
                a[r - 1] = a[r] + a[r - 1];
                r--;
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        int p = 1;
        for (int i = 0; i < n; i++) {
            if (a[i] > p)
                break;
            else
                p += a[i];
        }
        System.out.println(p);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n <= 2) System.out.println(0);
        else {
            int pre2 = 0, pre1 = 1;
            for (int i = 3; i < n; i++) {
                int sum = pre2 + pre1;
                if (sum == n){
                    System.out.println(0);
                    break;
                }
                else if (pre1 < n && n < sum){
                    System.out.println(Math.min(n - pre1, sum - n));
                    break;
                }
                pre2 = pre1;
                pre1 = sum;
            }
        }
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        if (isUpper(s) && secJudge(s) && thirdJudge(s))
            System.out.println("Likes");
        else
            System.out.println("Dislikes");
    }

    public static boolean isUpper(String s){
        return s.matches("[A-Z]+");
    }

    public static boolean secJudge(String s){
        return !s.matches(".*(.)\\1.*");
    }

    public static boolean thirdJudge(String s){
        return !s.matches(".*(.).*(.)\\1.*\\2.*");
    }
}

// \1的意思是，和第一个()里的内容相同，注意转义字符的处理并且必须和()配套使用。
// \2的用法同理。

// .:匹配除换行符以外的任意字符
// *:重复零次或更多次
// +:重复一次或更多次

100
5
77 92
22 22
29 36
50 46
99 90

输出
114

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 完全背包
        Scanner sc = new Scanner(System.in);
        int W = sc.nextInt();
        int n = sc.nextInt();
        int[] ps = new int[n];
        int[] vs = new int[n];
        for (int i = 0; i < n; i++) {
            ps[i] = sc.nextInt();
            vs[i] = sc.nextInt();
        }

        int[] dp = new int[W + 1];
        for (int i = 1; i <= n; i++) {
            int p = ps[i - 1], v = vs[ i - 1];
            for (int j = p; j <= W; j++) {
                dp[j] = Math.max(dp[j], dp[j - p] + v);
            }
        }
        System.out.println(dp[W]);
    }
}

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<String> ret = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s  = sc.nextLine();
        String ss = convertNumber(s);

        char[] chars = ss.toCharArray();
        dfs(chars, new boolean[chars.length], new StringBuilder());
        int cnt = 0;
        for (String s1 : ret) {
            int num = Integer.parseInt(s1);
            if (num % 7 == 0)
                cnt++;
        }
        System.out.println(cnt);
    }

    public static void dfs(char[] chars, boolean[] marked, StringBuilder s){
        if (s.length() == chars.length){
            ret.add(s.toString());
            return;
        }
        for (int i = 0; i < marked.length; i++) {
            if (marked[i])
                continue;

            marked[i] = true;
            s.append(chars[i]);
            dfs(chars, marked, s);
            marked[i] = false;
            s.deleteCharAt(s.length() - 1);
        }
    }

    public static String convertNumber(String s){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9')
                sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        boolean lenFlag = true;
        List<String> v = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            v.add(sc.nextLine());
        }
        List<String> p = new ArrayList<>(v);
        Collections.sort(p);
        boolean dictFlag = p.equals(v);
        for (int i = 1; i < n; i++) {
            if (v.get(i).length() < v.get(i - 1).length()){
                lenFlag = false;
                break;
            }
        }

        if (dictFlag && lenFlag)
            System.out.println("both");
        else if (lenFlag)
            System.out.println("lengths");
        else if (dictFlag)
            System.out.println("lexicographically");
        else
            System.out.println("none");
    }
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        String b = sc.nextLine();
        int cnt = 0;
        for (int i = 0; i < a.length(); i++) {
            String s = a.substring(0, i + 1) + b + a.substring(i + 1);
            if (isSym(s))
                cnt++;
        }
        if (isSym(b+a))
            cnt++;
        System.out.println(cnt);
    }

    public static boolean isSym(String s){
        int l = 0, r = s.length() - 1;
        while (l < r){
            if (s.charAt(l) != s.charAt(r)){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] nums = new int[n][2];
        for (int i = 0; i < n; i++) {
            nums[i][0] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            nums[i][1] = sc.nextInt();
        }
        Arrays.sort(nums, (a, b) -> (a[0] + a[1]) - (b[0] + b[1]));
        System.out.println((nums[0][0] - 1) + nums[0][1] - 1);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int w = sc.nextInt();
        int h = sc.nextInt();
        int[][] a = new int[w][h];
        int cnt = 0;
        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                if (a[i][j] == 0){
                    cnt++;
                    if ((i + 2) < w)
                        a[i + 2][j] = -1;
                    if ((j + 2) < h)
                        a[i][j + 2] = -1;
                }
            }
        }
        System.out.println(cnt);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        long min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            if (x > max1){
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x > max2){
                max3 = max2;
                max2 = x;
            } else if (x > max3)
                max3 = x;
            if (x < min1){
                min2 = min1;
                min1 = x;
            } else if (x < min2)
                min2 = x;
        }
        System.out.println(Math.max(max1 * max2 * max3, max1 * min1 * min2));
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int[] hs = new int[h];
        for (int i = 0; i < h; i++) {
            hs[i] = sc.nextInt();
        }
        int w = sc.nextInt();
        int[] ws = new int[w];
        for (int i = 0; i < w; i++) {
            ws[i] = sc.nextInt();
        }
        Arrays.sort(hs);
        Arrays.sort(ws);
        int i = 0, j = 0;
        while (i < h && j < w){
            if (hs[i] <= ws[j])
                i++;
            j++;
        }
        System.out.println(i);
    }
}

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String t = sc.nextLine();
        if (isSeq(s, t))
            System.out.println("Yes");
        else
            System.out.println("No");
    }

    public static boolean isSeq(String s, String t){
        if (t.equals(" "))
            return true;
        int inx = -1;
        for (char c : t.toCharArray()) {
            inx = s.indexOf(c, inx + 1);
            if (inx == -1) return false;
        }
        return true;
    }

}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sum = 0;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            sum += a[i];
        }
        System.out.println(minCount(a, sum));
    }

    public static int minCount(int[] a, int sum){
        if (sum % a.length != 0)
            return -1;
        int avg = sum / a.length;
        int cnt = 0;
        for (int i = 0; i < a.length; i++) {
            int sub = a[i] - avg;
            if (sub > 0){
                if (sub % 2 == 0)
                    cnt += sub / 2;
                else
                    return -1;
            }
        }
        return cnt;
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        System.out.println(min(a, n));
    }

    public static int min(int[] a, int n){
        for (int i = n - 1; i >= 0; i--) {
            Arrays.sort(a);
            for (int j = i - 1; j >= 0; j--) {
                if ((a[i] ^ a[j]) < a[j])
                    a[j] ^= a[i];
            }
        }
        int cnt = 0;
        for (int i : a) {
            if (i != 0)
                cnt++;
        }
        return cnt;
    }
}