Given an array a of length n, find another array, b, of length n such that:

  * for each i (1 ≤ i ≤ n) MEX(\\{b_1, b_2, …, b_i\})=a_i. 



The MEX of a set of integers is the smallest non-negative integer that doesn't belong to this set.

If such array doesn't exist, determine this.

Input

The first line contains an integer n (1 ≤ n ≤ 10^5) — the length of the array a.

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ i) — the elements of the array a. It's guaranteed that a_i ≤ a_{i+1} for 1≤ i < n.

Output

If there's no such array, print a single line containing -1.

Otherwise, print a single line containing n integers b_1, b_2, …, b_n (0 ≤ b_i ≤ 10^6)

If there are multiple answers, print any.

Examples

Input


3
1 2 3


Output


0 1 2 

Input


4
0 0 0 2


Output


1 3 4 0 

Input


3
1 1 3


Output


0 2 1 

Note

In the second test case, other answers like [1,1,1,0], for example, are valid.
import java.io.*;
import java.util.*;

public class R649C {

	public static void main(String[] args) {
		JS scan = new JS();
		int n = scan.nextInt();
		int[] arr =new int[n];
		PrintWriter out =new PrintWriter(System.out);
		int highest = 0;
		HashSet<Integer> bad = new HashSet<>();
		HashSet<Integer> answ = new HashSet<>();
		for(int i =0;i<n;i++) {
			arr[i]= scan.nextInt();
			bad.add(arr[i]);
			highest = Math.max(highest, arr[i]);
		}
		int[] next = new int[n];
		//finds the index of the next number higher than this
		for(int i = n-2;i>=0;i--) {
			if(arr[i]==arr[i+1])next[i] = next[i+1];
			else next[i] = arr[i+1];
		}
		highest--;
		int[] ans =new int[n];
		int count = 0;
		int lowest = 0;
		loop:for(int i = 0;i<n;i++) {
			boolean pass= false;
			if(i>0)
				if(arr[i]!=arr[i-1])highest = next[i];
			if((arr[i]==0 && i==0))pass = true;
			if(i>0 || (i==0 && pass)) {
				if(pass ||(arr[i]==arr[i-1] || lowest>=arr[i])) {
					for(;highest>arr[i];highest--) {
						if(!bad.contains(highest)) {
							ans[i] = highest;
							bad.add(highest);
							answ.add(highest);
							continue loop;
						}
					}
					highest = arr[n-1];
					for(;highest>arr[i];highest--) {
						if(!bad.contains(highest)) {
							ans[i] = highest;
							bad.add(highest);
							answ.add(highest);
							continue loop;
						}
					}
					if(i>0) {
						ans[i] = ans[i-1];
						continue;
					}
				}
			}
			int temp = lowest;
			boolean badd = false;
			while(answ.contains(lowest) || lowest==arr[i]) {
				if(lowest ==arr[i]) badd= true;
				lowest++;
			}
			ans[i] = lowest;
			bad.add(ans[i]);
			answ.add(ans[i]);
			if(badd)lowest = temp;
		}
		/*
6
1 2 2 3 3 6	
15
1 1 1 2 2 2 3 3 3 4 4 4 5 5 15	

5
1 2 2 4 5

6
1 2 2 2 4 5
		 */

		//1 2 3 3 4 6
		//0 1 2 5 3 4
		//1 2 3 4 5
		//1 2 2 2 5 5 7
		//0 1 2 3 4
		for(int i = 0;i<n;i++) {
			if(arr[i]>i+1) {
				out.println(-1);
				out.flush();
				out.close();
				return;
			}
		}
		for(Integer curr:ans) {
			out.print(curr+" ");
		}
		out.println();
		out.flush();
		out.close();
	}
	static class JS{
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public JS() {
			in = new BufferedInputStream(System.in, BS);
		}

		public JS(String s) throws FileNotFoundException {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}				
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
	}
}