Problem: This is the easy version of the problem. The difference between the versions is that in the easy version all prices a_i are different. You can make hacks if and only if you solved both versions of the problem.

Today is Sage's birthday, and she will go shopping to buy ice spheres. All n ice spheres are placed in a row and they are numbered from 1 to n from left to right. Each ice sphere has a positive integer price. In this version all prices are different.

An ice sphere is cheap if it costs strictly less than two neighboring ice spheres: the nearest to the left and the nearest to the right. The leftmost and the rightmost ice spheres are not cheap. Sage will choose all cheap ice spheres and then buy only them.

You can visit the shop before Sage and reorder the ice spheres as you wish. Find out the maximum number of ice spheres that Sage can buy, and show how the ice spheres should be reordered.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of ice spheres in the shop.

The second line contains n different integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the prices of ice spheres.

Output

In the first line print the maximum number of ice spheres that Sage can buy.

In the second line print the prices of ice spheres in the optimal order. If there are several correct answers, you can print any of them.

Example

Input


5
1 2 3 4 5


Output


2
3 1 4 2 5 

Note

In the example it's not possible to place ice spheres in any order so that Sage would buy 3 of them. If the ice spheres are placed like this (3, 1, 4, 2, 5), then Sage will buy two spheres: one for 1 and one for 2, because they are cheap.

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task solver = new Task();
		int i = 0;
//		int t = in.nextInt();
//		for (; i < t; i++)
		solver.solve(i, in, out);

		out.close();

	}

	static class Task {
		static ArrayList<ArrayList<Integer>> adj;
		static ArrayList<Boolean> visited;

		static long hash(ArrayList<Integer> al) {
			long cur = 0;
			for (Integer i : al) {
				cur += (cur * 30001) + i;
			}
			return cur + al.size();
		}

		public void solve(int testNumber, InputReader in, PrintWriter out) throws IOException {

			int n = in.nextInt();
			int arr[] = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = in.nextInt();
			}
			Arrays.sort(arr);
			int mid = 0;
			int to = n - 1, from = 0;
			int best = 0;
			while (to >= from) {
				mid = (from + to) / 2;
				int j = 0;
				boolean isAnswer = true;
				for (int i = n - 1; j < mid; i--) {
					if (arr[i] <= arr[j] || arr[i - 1] <= arr[j]) {
						isAnswer = false;
						break;
					}
					j++;
				}
				if (isAnswer) {
					if (mid > best)
						best = mid;
					from = mid + 1;
				} else {
					to = mid - 1;
				}

			}

			int j = 0;
			System.out.println(best);

			int count = 0;
			for (int i = 0; count < n; i++) {
				if(count<n) {
					System.out.print(arr[n-i-1]+" ");
					count++;
				}
				if(count<n) {
					System.out.print(arr[i]+" ");
					count++;
				}
			}
			

		}

		public static int min(int a, int b) {
			return (a > b) ? b : a;
		}

		public static void dfs(int v) {
			visited.set(v - 1, true);
			for (Integer i : adj.get(v - 1)) {
				if (!visited.get(i - 1))
					dfs(i - 1);
			}
		}

		static long modInverse(long a, int m) {
			long g = gcd(a, m);
			if (g != 1) {
				System.out.println("Inverse doesn't exist");
				return 0;
			} else {
				// If a and m are relatively prime, then modulo inverse
				// is a^(m-2) mode m
				return power(a, m - 2, m);
			}
		}

		// To compute x^y under modulo m
		static long power(long x, long y, long m) {
			if (y == 0)
				return 1;

			long p = power(x, y / 2, m) % m;
			p = (p * p) % m;

			if (y % 2 == 0)
				return p;
			else
				return (x * p) % m;
		}

		// Function to return gcd of a and b
		static long gcd(long a, long b) {
			if (a == 0)
				return b;
			return gcd(b % a, a);
		}

		static int highestPowerOf2(int n) {
			return (n & (~(n - 1)));
		}

	}
	// template code

	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

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

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

		public double nextDouble() {
			return Double.parseDouble(next());
		}

	}

}

class Point {
	double x, y;

	public Point(double x, double y) {
		this.x = x;
		this.y = y;
	}

	public double d(Point p2) {

		return Math.sqrt(Math.pow(p2.x - this.x, 2) + Math.pow(p2.y - this.y, 2));
	}

	public Point mp(Point p2) {
		return new Point((p2.x + this.x) / 2, (p2.y + this.y) / 2);
	}
}

class TCS {
	long i1, i2;
	int flag;

	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return "i1:" + i1 + "  i2:" + i2;
	}

	TCS(long i1, long i2) {
		this.i1 = i1;
		this.i2 = i2;
	}

}

class Pair implements Comparator<Pair>, Comparable<Pair> {
	double key, value;

	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return "key:" + key + " value: " + value;
	}

	public Pair(double i, double j) {
		key = i;
		value = j;

	}

	@Override
	public int compare(Pair o1, Pair o2) {
		// TODO Auto-generated method stub
		return o1.compareTo(o2);
	}

	@Override
	public int hashCode() {
		// TODO Auto-generated method stub
		return (int) (key * 1234 + value * 4321);
	}

	@Override
	public int compareTo(Pair o) {
		// TODO Auto-generated method stub
		return (int) (this.key - o.key);
	}

}