Bob is an active user of the social network Faithbug. On this network, people are able to engage in a mutual friendship. That is, if a is a friend of b, then b is also a friend of a. Each user thus has a non-negative amount of friends.

This morning, somebody anonymously sent Bob the following link: [graph realization problem](https://en.wikipedia.org/wiki/Graph_realization_problem) and Bob wants to know who that was. In order to do that, he first needs to know how the social network looks like. He investigated the profile of every other person on the network and noted down the number of his friends. However, he neglected to note down the number of his friends. Help him find out how many friends he has. Since there may be many possible answers, print all of them.

Input

The first line contains one integer n (1 ≤ n ≤ 5 ⋅ 10^5), the number of people on the network excluding Bob. 

The second line contains n numbers a_1,a_2, ..., a_n (0 ≤ a_i ≤ n), with a_i being the number of people that person i is a friend of.

Output

Print all possible values of a_{n+1} — the amount of people that Bob can be friend of, in increasing order.

If no solution exists, output -1.

Examples

Input

3
3 3 3


Output

3 


Input

4
1 1 1 1


Output

0 2 4 


Input

2
0 2


Output

-1


Input

35
21 26 18 4 28 2 15 13 16 25 6 32 11 5 31 17 9 3 24 33 14 27 29 1 20 4 12 7 10 30 34 8 19 23 22


Output

13 15 17 19 21 

Note

In the first test case, the only solution is that everyone is friends with everyone. That is why Bob should have 3 friends.

In the second test case, there are three possible solutions (apart from symmetries): 

  * a is friend of b, c is friend of d, and Bob has no friends, or 
  * a is a friend of b and both c and d are friends with Bob, or 
  * Bob is friends of everyone. 



The third case is impossible to solve, as the second person needs to be a friend with everybody, but the first one is a complete stranger.
import static java.lang.Math.*;
import java.io.*;
import java.util.*;

public class Problem2 {
    final static long mod = 1_000_000_007l;
    final static int maxn = 1_000_007;
    final static long infty = 1_000_000_009l;

    final static boolean DEBUG = true;
    // final static boolean DEBUG = false;

    // solve has the solution code

    static class Solver {

        Long[] d;
        Long[] As, Bp;
        Long[] A, B;
        Long[] sufm;
        Long[] pref;
        int n = 0;
        ArrayList<Long> soln;


        long S(long pos, long q) {
            int l = (int)pos, r = n + 1;
            d[n + 1] = 0l;
            while (l < r) {
                int m = (l + r - 1) / 2;
                if (q >= d[m]) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }

            return (pref[n] - pref[l - 1] + q * (l - pos));
        }

        public void solve() {

            n = in.gi();

            d = new Long[n + 2];
            pref = new Long[n + 2];
            As = new Long[n + 2];
            Bp = new Long[n + 2];
            A = new Long[n + 2];
            B = new Long[n + 2];
            soln = new ArrayList<>();

            for (int j = 1; j <= n; j++) 
                d[j] = in.gl();
        
            Arrays.sort(d, 1, n + 1, (x, y) -> y.compareTo(x));

            pref[0] = 0l;

            for (int j = 1; j <= n; j++) {
                pref[j] = pref[j - 1] + d[j];
            }

            for (int t = 1; t <= n; t++) {
                A[t] = S(t, t) + 1l * t * (t - 1) - pref[t - 1];
                B[t] = pref[t] - 1l * t * (t - 1) - S(t + 1, t);
                if (B[t] > t) {
                    println(-1);
                    return;
                }
            }
            Bp[0] = 0l;
            
            for (int t = 1; t <= n; t++) {
                Bp[t] = max(Bp[t - 1], B[t]);
            }
            As[n + 1] = 1l * n * (n + 1) - pref[n];
            for (int t = n; t >= 1; t--) {
                As[t] = min(As[t + 1], A[t]);
            }

            for (int j = 1; j <= n + 1; j++) {

                Long high = infty, low = 0l;
                if (j > 1) high = d[j - 1];
                if (j <= n) low = d[j];

                high = min(high, As[j]);
                low = max(low, Bp[j - 1]);

                for (long k = low; k <= high; k++) {
                    if (k % 2 == pref[n] % 2) {
                        soln.add(k);
                    }
                }
            }

            soln.sort(Long::compareTo);

            for (int j = 1; j < soln.size(); j++) {
                verify(soln.get(j - 1) <= soln.get(j));
            }

            long last = -1;

            for (int j = 0; j < soln.size(); j++) {
                if (j == 0 || soln.get(j) != last) {
                    print(soln.get(j), " ");
                    verify(last < 0 || last != soln.get(j));
                    last = soln.get(j);
                }
            }
            println();
        }




        PrintWriter out;
        FastInput in;
        Random random_source;

        void initRandom(Long x) {
            random_source = new Random(x);
        }

        void initRandom() {
            random_source = new Random(System.currentTimeMillis());
        }

        int randInt(int bound) { // [0..bound)
            return random_source.nextInt(bound);
        }

        int gcd(int x, int y) {
            while (y > 0) {
                int t = x % y;
                x = y; y = t;
            }
            return x;
        }

        void debug(Object... obj) {
            if (DEBUG) {
                out.print("# ");
                for (Object o : obj) {
                    out.print(o.toString());
                    out.print(" ");
                }
                out.println("");
                out.flush();
            }
        }

        void print(Object... obj) {
            for (Object o : obj) {
                out.print(o.toString());
            }
        }

        void println(Object... obj) {
            for (Object o : obj) {
                out.print(o.toString());
            }
            out.println("");
        } 

        void verify(boolean check) {    // equivalent to assert
            if (!check) {
                throw new RuntimeException("Verification error");
            }
        }

        Solver(PrintWriter out, FastInput in) {
            this.out = out; this.in = in;
        }
    }

    public static void main(String args[]) {
        FastInput in = new FastInput(System.in);
        PrintWriter out = new PrintWriter(System.out);
        Solver solver = new Solver(out, in);
        solver.solve();
        out.close();
    }
    
    static class FastInput {
        BufferedReader reader;
        StringTokenizer tok;

        public FastInput(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tok = null;
        }

        public String next() {
            while (tok == null || !tok.hasMoreTokens()) {
                try {
                    tok = new StringTokenizer(reader.readLine());
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
            return tok.nextToken();
        }

        public int gi() {
            return Integer.parseInt(next());
        }

        public long gl() {
            return Long.parseLong(next());
        }
    }

    static class Pair<A extends Comparable<A>, B extends Comparable<B>>
            implements Comparable<Pair<A, B>> {
        A F;
        B S;

        Pair(A x, B y) {
            F = x; S = y;
        }

        public boolean equals(Pair<A, B> oth) {
            return this.compareTo(oth) == 0;    
        }

        public int compareTo(Pair<A, B> Q) {
            if (this.F.compareTo(Q.F) == 0) {
                return this.S.compareTo(Q.S);
            } else {
                return this.F.compareTo(Q.F);
            }
        }

        public String toString() {
            return new StringBuilder("{")
                    .append(F.toString())
                    .append(", ")
                    .append(S.toString())
                    .append("}")
                    .toString();
        }
    }

    public static <A extends Comparable<A>, B extends Comparable<B>> Pair<A, B> make_pair(A a, B b) {
        return new Pair<A, B>(a, b);
    }

    static class IntPair extends Pair<Integer, Integer> {
        IntPair(Integer x, Integer y) {
            super(x, y);
        }
    }

    static class LongPair extends Pair<Long, Long> {
        LongPair(Long x, Long y) {
            super(x, y);
        }
    }
}
