public class Ld1171rdb045 {
	static int[] a, b;
	static int c, l, r, i, j, N;

	static Scanner input = new Scanner(System.in);

	public static void main(String[] args) {

	}

	public static void firstMethod(int[] a) {

		System.out.println("The amount of elements in the array A.");
		N = input.nextInt(); // N IS THE AMOUNT OF ELEMENTS IN THE ARRAY A

		a = new int[N];

		System.out.println("The values of the array A.");

		for (i = 0; i < a.length; i++) { // FILLING THE ARRAY A WITH VALUES
			a[i] = input.nextInt();
		}

		input.close();
		System.out.println(Arrays.toString(a)); // PRINTING OUT THE ARRAY A TO CHECK

		b = new int[2 * N - 1]; // CREATING TWICE BIGGER[-1] ARRAY B

		l = N - 1; // ASSIGNING AS A MIDDLE ELEMENT
		r = N - 1; // ASSIGNING AS A MIDDLE ELEMENT

		b[r] = a[0]; // THE FIRST VALUE OF THE ARRAY B IS NOW IN THE MIDDLE OF THE ARRAY B

		for (i = 1; i < N; i++) { // LOOP THROUGH THE ARRAY

			if (b[l] > a[i]) { // IF THE LEFT VALUE IS BIGGER THAN a[i] THEN DECREMENT LEFT AND ASSIGN a[i] TO THE LEFT VALUE
				l--;
				b[l] = a[i];

			} else if (b[r] < a[i]) { // IF THE LEFT VALUE IS BIGGER THAN a[i] THEN INCREMENT RIGHT AND ASSIGN a[i] TO THE RIGHT VALUE

				r++;
				b[r] = a[i];
			} else { // ( I GUESS THE PROBLEM IS HERE)

				for (j = l; j < r; j++) { // LOOP THROUGH THE ARRAY B
					if (b[j] >= a[i]) { // IF THE LEFT VALUE IS BIGGER THAN a[i]

						if (j - l <= r - j) { IF THERE ARE LESS ELEMENTS ON THE LEFT SIDE

							for (int k = b[l]; k <= b[j - 1]; k++) { // SHIFT ALL ELEMENTS ONE POSITION TO THE LEFT
								b[k - 1] = b[k];
							}
							l--;
							b[j - 1] = a[i];
						}

						if (j - l >= r - j) { IF THERE ARE LESS ELEMENTS ON THE RIGHT SIDE
							for (int k = b[r]; k >= b[j]; k--) { // SHIFT ALL ELEMENTS ONE POSITION TO THE RIGHT
								b[k + 1] = b[k];
							}
							r++;
							b[j] = a[i];

						}
					}
				}

				if (b[j] <= a[i]) { // NOT SURE IF THIS ONE IS EVEN NEEDED BUT BASICALLY DO THE SAME THING IF VALUE IS SMALLER THAN a[i]
					if (j - l <= r - j) {

						for (int k = b[l]; k <= b[j - 1]; k++) {
							b[k - 1] = b[k];
						}
						l--;
						b[j - 1] = a[i];
					}

					if (j - l >= r - j) {
						for (int k = b[r]; k >= b[j]; k--) {
							b[k + 1] = b[k];
						}
						r++;
						b[j] = a[i];

					}
				}
			}
		}

		System.out.println(Arrays.toString(b)); // PRINT OUT THE ARRAY B

	}