Do you like summer? Residents of Berland do. They especially love eating ice cream in the hot summer. So this summer day a large queue of n Berland residents lined up in front of the ice cream stall. We know that each of them has a certain amount of berland dollars with them. The residents of Berland are nice people, so each person agrees to swap places with the person right behind him for just 1 dollar. More formally, if person a stands just behind person b, then person a can pay person b 1 dollar, then a and b get swapped. Of course, if person a has zero dollars, he can not swap places with person b.

Residents of Berland are strange people. In particular, they get upset when there is someone with a strictly smaller sum of money in the line in front of them.

Can you help the residents of Berland form such order in the line so that they were all happy? A happy resident is the one who stands first in the line or the one in front of who another resident stands with not less number of dollars. Note that the people of Berland are people of honor and they agree to swap places only in the manner described above.

Input

The first line contains integer n (1 ≤ n ≤ 200 000) — the number of residents who stand in the line.

The second line contains n space-separated integers ai (0 ≤ ai ≤ 109), where ai is the number of Berland dollars of a man standing on the i-th position in the line. The positions are numbered starting from the end of the line. 

Output

If it is impossible to make all the residents happy, print ":(" without the quotes. Otherwise, print in the single line n space-separated integers, the i-th of them must be equal to the number of money of the person on position i in the new line. If there are multiple answers, print any of them.

Examples

Input

2
11 8


Output

9 10 

Input

5
10 9 7 10 6


Output

:(


Input

3
12 3 3


Output

4 4 10 

Note

In the first sample two residents should swap places, after that the first resident has 10 dollars and he is at the head of the line and the second resident will have 9 coins and he will be at the end of the line. 

In the second sample it is impossible to achieve the desired result.

In the third sample the first person can swap with the second one, then they will have the following numbers of dollars: 4 11 3, then the second person (in the new line) swaps with the third one, and the resulting numbers of dollars will equal to: 4 4 10. In this line everybody will be happy.

import java.io.*;
import java.math.*;
import java.util.*;

import static java.util.Arrays.*;

public class G {
	private static final int mod = (int)1e9+7;

	final Random random = new Random(0);
	final IOFast io = new IOFast();

	/// MAIN CODE
	public void run() throws IOException {
//		int TEST_CASE = Integer.parseInt(new String(io.nextLine()).trim());
		int TEST_CASE = 1;
		while(TEST_CASE-- != 0) {
			int n = io.nextInt();
			int[] a = new int[n];
			Seg2 seg = new Seg2(n);
			for(int i = 0; i < n; i++) {
				a[i] = io.nextInt();
//				a[i] = random.nextInt(1000000000+1);
				seg.update(i, a[i] - (n - 1 - i));
			}
			
			int[] ans = new int[n];
			for(int i = n - 1; i >= 0; i--) {
				int idx = seg.getIndex(0, n);
//				System.err.println(i + " " + idx + " " + seg.get(idx, idx + 1) + " " + seg.get(0, n));
				seg.update(idx, Integer.MIN_VALUE);
				ans[i] = a[idx] - (i - idx);
			}
			
			for(int i = 0; i < n - 1; i++) {
				if(ans[i] > ans[i+1]) {
					io.out.println(":(");
					return;
				}
			}
			
			for(int i = 0; i < n; i++) {
				io.out.print(ans[i] + (i==n-1?"\n":" "));
			}
		}
	}
	
	static
	class Seg2 {
		final int n;
		final int[] seg;
		
		public Seg2(final int n) {
			this.n = Integer.highestOneBit(n) << 1;
			seg = new int[this.n << 1];
			Arrays.fill(seg, Integer.MIN_VALUE);
		}

		int get(int l, int r) { return get(l, r, 0, 0, n); }
		int get(int l, int r, int k, int curL, int curR) {
			if(curR <= l || curL >= r) return 0;
			if(l <= curL && curR <= r) { return seg[k]; }
			final int curM = (curL + curR) / 2;
			return Math.max(
					get(l, r, 2 * k + 1, curL, curM),
					get(l, r, 2 * k + 2, curM, curR));
		}

		int getIndex(int l, int r) { return getIndex(l, r, 0, 0, n) - (n - 1); }
		int getIndex(int l, int r, int k, int curL, int curR) {
			if(curR - curL == 1) return k;
			
			final int curM = (curL + curR) / 2;
			if(seg[2*k+1] > seg[2*k+2]) return getIndex(l, r, 2 * k + 1, curL, curM);
			else return getIndex(l, r, 2 * k + 2, curM, curR);
			/*
			if(curR <= l || curL >= r) return 0;
			if(l <= curL && curR <= r) { return seg[k]; }
			final int curM = (curL + curR) / 2;
			return Math.max(
					get(l, r, 2 * k + 1, curL, curM),
					get(l, r, 2 * k + 2, curM, curR));
					*/
		}
		
		void update(int i, int v) {
			i += n - 1;
			seg[i] = v;
			while(i != 0) {
				i = (i - 1) / 2;
				seg[i] = Math.max(seg[2*i+1], seg[2*i+2]);
			}
		}
	}

	static
	class SegRMQInt {
		final int INF = 1<<29;
		
		final int n;
		final int[] seg;
		final int[] add;
		
		public SegRMQInt(final int n) {
			this.n = Integer.highestOneBit(n) << 1;
			seg = new int[this.n << 1];
			add = new int[this.n << 1];
			Arrays.fill(seg, INF);
		}
		
		void propagate(int curL, int curR, int k) {
			if(add[k] != 0) {
				final int curM = (curL + curR) / 2;
				add(curL, curR, 2 * k + 1, add[k], curL, curM);
				add(curL, curR, 2 * k + 2, add[k], curM, curR);
				add[k] = 0;
			}
		}

		int get(int l, int r) { return get(l, r, 0, 0, n); }
		int get(int l, int r, int k, int curL, int curR) {
			if(curR <= l || curL >= r) return INF;
			if(l <= curL && curR <= r) { return seg[k]; }
			propagate(curL, curR, k);
			final int curM = (curL + curR) / 2;
			return Math.min(
					get(l, r, 2 * k + 1, curL, curM),
					get(l, r, 2 * k + 2, curM, curR));
		}

		int getIndex(int l, int r) { return getIndex(l, r, 0, 0, n) - (n - 1); }
		int getIndex(int l, int r, int k, int curL, int curR) {
//			System.err.println(k);
			if(curR <= l || curL >= r) return -1;
			if(curR - curL == 1) return k;
			propagate(curL, curR, k);
			final int curM = (curL + curR) / 2;
			if(l <= curL && curR <= r) {
				if(seg[k] == seg[2*k+0]) return getIndex(l, r, 2 * k + 1, curL, curM);
				else return getIndex(l, r, 2 * k + 2, curM, curR);
			}
			int i0 = getIndex(l, r, 2 * k + 1, curL, curM);
			int i1 = getIndex(l, r, 2 * k + 2, curM, curR);
			if(i0 == -1) return i1;
			if(i1 == -1) return i0;
			return seg[i0] < seg[i1] ? i0 : i1;
		}

		void add(int l, int r, int v) { add(l, r, 0, v, 0, n); }
		void add(int l, int r, int k, int v, int curL, int curR) {
			if(curR <= l || curL >= r) return;
			if(l <= curL && curR <= r) { seg[k] += v; add[k] += v; return; }
			final int curM = (curL + curR) / 2;
			propagate(curL, curR, k);
			add(l, r, 2 * k + 1, v, curL, curM);
			add(l, r, 2 * k + 2, v, curM, curR);
			seg[k] = Math.min(seg[2*k+1], seg[2*k+2]);
		}
		
		void set(int i, int v) {
			// propagate to leaf
//			add(i, i + 1, 0);
			
			i += n - 1;
			seg[i] = v;
			add[i] = 0;
			while(i != 0) {
				i = (i - 1) / 2;
				seg[i] = Math.min(seg[2*i+1], seg[2*i+2]) + add[i];
			}
		}
		
		void set2(int i, int v) {
			// propagate to leaf
			add(i, i + 1, 0);
			
			i += n - 1;
			seg[i] = v;
			add[i] = 0;
			while(i != 0) {
				i = (i - 1) / 2;
				seg[i] = Math.min(seg[2*i+1], seg[2*i+2]) + add[i];
			}
		}
	}


	/// TEMPLATE
	static int gcd(int n, int r) { return r == 0 ? n : gcd(r, n%r); }
	static long gcd(long n, long r) { return r == 0 ? n : gcd(r, n%r); }
	
	static <T> void swap(T[] x, int i, int j) { T t = x[i]; x[i] = x[j]; x[j] = t; }
	static void swap(int[] x, int i, int j) { int t = x[i]; x[i] = x[j]; x[j] = t; }
	
	void main() throws IOException {
		//		IOFast.setFileIO("rle-size.in", "rle-size.out");
		try { run(); }
		catch (EndOfFileRuntimeException e) { }
		io.out.flush();
	}
	public static void main(String[] args) throws IOException { new G().main(); }
	
	static class EndOfFileRuntimeException extends RuntimeException {
		private static final long serialVersionUID = -8565341110209207657L; }

	static
	public class IOFast {
		private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		private PrintWriter out = new PrintWriter(System.out);

		void setFileIn(String ins) throws IOException { in.close(); in = new BufferedReader(new FileReader(ins)); }
		void setFileOut(String outs) throws IOException { out.flush(); out.close(); out = new PrintWriter(new FileWriter(outs)); }
		void setFileIO(String ins, String outs) throws IOException { setFileIn(ins); setFileOut(outs); }

		private static int pos, readLen;
		private static final char[] buffer = new char[1024 * 8];
		private static char[] str = new char[500*8*2];
		private static boolean[] isDigit = new boolean[256];
		private static boolean[] isSpace = new boolean[256];
		private static boolean[] isLineSep = new boolean[256];

		static { for(int i = 0; i < 10; i++) { isDigit['0' + i] = true; } isDigit['-'] = true; isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true; isLineSep['\r'] = isLineSep['\n'] = true; }
		public int read() throws IOException { if(pos >= readLen) { pos = 0; readLen = in.read(buffer); if(readLen <= 0) { throw new EndOfFileRuntimeException(); } } return buffer[pos++]; }
		public int nextInt() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; int ret = 0; if(str[0] == '-') { i = 1; } for(; i < len; i++) ret = ret * 10 + str[i] - '0'; if(str[0] == '-') { ret = -ret; } return ret; }
		public long nextLong() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); int i = 0; long ret = 0; if(str[0] == '-') { i = 1; } for(; i < len; i++) ret = ret * 10 + str[i] - '0'; if(str[0] == '-') { ret = -ret; } return ret; }
		public char nextChar() throws IOException { while(true) { final int c = read(); if(!isSpace[c]) { return (char)c; } } }
		int reads(int len, boolean[] accept) throws IOException { try { while(true) { final int c = read(); if(accept[c]) { break; } if(str.length == len) { char[] rep = new char[str.length * 3 / 2]; System.arraycopy(str, 0, rep, 0, str.length); str = rep; } str[len++] = (char)c; } } catch(EndOfFileRuntimeException e) { ; } return len; }
		int reads(char[] cs, int len, boolean[] accept) throws IOException { try { while(true) { final int c = read(); if(accept[c]) { break; } cs[len++] = (char)c; } } catch(EndOfFileRuntimeException e) { ; } return len; }
		public char[] nextLine() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isLineSep); try { if(str[len-1] == '\r') { len--; read(); } } catch(EndOfFileRuntimeException e) { ; } return Arrays.copyOf(str, len); }
		public String nextString() throws IOException { return new String(next()); }
		public char[] next() throws IOException { int len = 0; str[len++] = nextChar(); len = reads(len, isSpace); return Arrays.copyOf(str, len); }
		public int next(char[] cs) throws IOException { int len = 0; cs[len++] = nextChar(); len = reads(cs, len, isSpace); return len; }
		public double nextDouble() throws IOException { return Double.parseDouble(nextString()); }
		public long[] nextLongArray(final int n) throws IOException { final long[] res = new long[n]; for(int i = 0; i < n; i++) { res[i] = nextLong(); } return res; }
		public int[] nextIntArray(final int n) throws IOException { final int[] res = new int[n]; for(int i = 0; i < n; i++) { res[i] = nextInt(); } return res; }
		public int[][] nextIntArray2D(final int n, final int k) throws IOException { final int[][] res = new int[n][]; for(int i = 0; i < n; i++) { res[i] = nextIntArray(k); } return res; }
		public int[][] nextIntArray2DWithIndex(final int n, final int k) throws IOException { final int[][] res = new int[n][k+1]; for(int i = 0; i < n; i++) { for(int j = 0; j < k; j++) { res[i][j] = nextInt(); } res[i][k] = i; } return res; }
		public double[] nextDoubleArray(final int n) throws IOException { final double[] res = new double[n]; for(int i = 0; i < n; i++) { res[i] = nextDouble(); } return res; }
	}
}
