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.max;
import static java.lang.Math.min;
import static java.util.Arrays.*;
import static java.util.Collections.*;

import java.util.*;
import java.util.ArrayList;

public class E {

	public Object solve () {
		int N = sc.nextInt();
		int [] D = sort(sc.nextInts(), reverseOrder());

		long SUM = stream(D).mapToLong(x -> x).sum();

		long [] C = new long [N+1], Z = new long [N+1];
		for (int j : rep(N)) {
			++C[min(j, D[j])];
			if (D[j] > 0)
				++Z[min(j, D[j] - 1)];
		}

		for (int k : sep(N)) {
			C[k] += C[k+1];
			Z[k] += Z[k+1];
		}

		long [] S = new long [N+1], T = new long [N+1];
		for (int k : rep(N)) {
			S[k+1] = S[k] + D[k];
			T[k+1] = T[k] + 2*k + C[k+1] - min(k, D[k]);
		}

		boolean [] Q = new boolean [N+1];
		long [] A = new long [N+1], B = new long [N+1];
		
		for (int k : req(N)) {
			A[k] = S[k] - T[k];
			Q[k] = A[k] <= k;
			if (k > 0) {
				A[k] = max(A[k], A[k-1]);
				Q[k] = Q[k] && Q[k-1];
			}
		}

		for (int k : seq(N)) {
			B[k] = T[k] - S[k] + 2*k + Z[k];
			if (k < N)
				B[k] = min(B[k], B[k+1]);
		}

		boolean [] V = new boolean [N+1];

		for (int M : req(N))
			if (Q[M]) {
				int max = (int) min(M == 0 ? N : D[M-1], B[M]);
				int min = (int) max(M == N ? 0 : D[M], A[M]);
				for (int j : req(min, max))
					if ((SUM + j) % 2 == 0)
						V[j] = true;
			}

		List<Integer> res = new ArrayList<>();
		for (int i : req(N))
			if (V[i])
				res.add(i);

		return exit(res.isEmpty() ? -1 : res);
	}

	private static final boolean ONE_TEST_CASE = true;

	private static void init () {
	}

	private static Integer [] obj (int ... A) { return stream(A).mapToObj(x -> x).toArray(Integer[]::new); }
	private static int [] pri (Integer [] A) { return stream(A).mapToInt(x -> x).toArray(); }
	private static int [] pri (Integer [] A, int [] a) { System.arraycopy(pri(A), 0, a, 0, A.length); return a; }
	private static int [] rep (int N) { return rep(0, N); }
	private static int [] rep (int S, int T) { if (S >= T) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static int [] req (int N) { return req(0, N); }
	private static int [] req (int S, int T) { return rep(S, T+1); }
	private static int [] sep (int N) { return sep(0, N); }
	private static int [] sep (final int S, final int T) { if (S >= T) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[T-1-i] = i; return res; }
	private static int [] seq (int N) { return seq(0, N); }
	private static int [] seq (int S, int T) { return sep(S, T+1); }
	private static int [] sort (int [] A, Comparator<Integer> C) { Integer [] AA = obj(A); Arrays.sort(AA, C); return pri(AA, A); }
	//////////////////////////////////////////////////////////////////////////////////// OFF
	private static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static Object print (Object o, Object ... A) { IOUtils.print(o, A); return null; }
	private static Object exit (Object o, Object ... A) { print(o, A); IOUtils.exit(); return null; }
	private static class IOUtils {
		public static class MyScanner {
			public String next () { newLine(); return line[index++]; }
			public int nextInt () { return Integer.parseInt(next()); }
			public String nextLine () { line = null; return readLine(); }
			public String [] nextStrings () { return split(nextLine()); }
			public int[] nextInts () { return nextStream().mapToInt(Integer::parseInt).toArray(); }
			//////////////////////////////////////////////
			private boolean eol () { return index == line.length; }
			private String readLine () {
				try {
					return r.readLine();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private final java.io.BufferedReader r;
			private MyScanner () { this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in))); }
			private MyScanner (java.io.BufferedReader r) {
				try {
					this.r = r;
					while (!r.ready())
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine () {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private java.util.stream.Stream<String> nextStream () { return java.util.Arrays.stream(nextStrings()); }
			private String [] split (String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build (Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim (String delim, Object o, Object ... A) {
			StringBuilder b = new StringBuilder();
			append(b, o, delim);
			for (Object p : A)
				append(b, p, delim);
			return b.substring(delim.length());
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static final java.text.DecimalFormat formatter = new java.text.DecimalFormat("#.#########");
		private static void start () { if (t == 0) t = millis(); }
		private static void append (java.util.function.Consumer<Object> f, java.util.function.Consumer<Object> g, final Object o) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					f.accept(java.lang.reflect.Array.get(o, i));
			}
			else if (o instanceof Iterable<?>)
				((Iterable<?>)o).forEach(f::accept);
			else
				g.accept(o instanceof Double ? formatter.format(o) : o);
		}
		private static void append (final StringBuilder b, Object o, final String delim) {
			append(x -> { append(b, x, delim); }, x -> b.append(delim).append(x), o);
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static void print (Object o, Object ... A) {
			pw.println(build(o, A));
			if (DEBUG)
				pw.flush();
		}
		private static void err (Object o, Object ... A) { System.err.println(build(o, A)); }
		private static boolean DEBUG;
		private static void write (Object o) {
			err(o, '(', time(), ')');
			if (!DEBUG)
				pw.println(o);
		}
		private static void exit () {
			IOUtils.pw.close();
			System.out.flush();
			err("------------------");
			err(time());
			System.exit(0);
		}
		private static long t;
		private static long millis () { return System.currentTimeMillis(); }
		private static String time () { return "Time: " + (millis() - t) / 1000.0; }
		private static void run (int N) {
			try { DEBUG = System.getProperties().containsKey("DEBUG"); }
			catch (Throwable t) {}

			for (int n = 1; n <= N; ++n) {
				Object res = new E().solve();
				if (res != null)
					write("Case #" + n + ": " + build(res));
			}
			exit();
		}
	}
	////////////////////////////////////////////////////////////////////////////////////
	public static void main (String[] args) {
		init();
		int N = ONE_TEST_CASE ? 1 : sc.nextInt();
		IOUtils.run(N);
	}
}
