In the official contest this problem has a different statement, for which jury's solution was working incorrectly, and for this reason it was excluded from the contest. This mistake have been fixed and the current given problem statement and model solution corresponds to what jury wanted it to be during the contest.

Vova and Lesha are friends. They often meet at Vova's place and compete against each other in a computer game named The Ancient Papyri: Swordsink. Vova always chooses a warrior as his fighter and Leshac chooses an archer. After that they should choose initial positions for their characters and start the fight. A warrior is good at melee combat, so Vova will try to make the distance between fighters as small as possible. An archer prefers to keep the enemy at a distance, so Lesha will try to make the initial distance as large as possible.

There are n (n is always even) possible starting positions for characters marked along the Ox axis. The positions are given by their distinct coordinates x1, x2, ..., xn, two characters cannot end up at the same position.

Vova and Lesha take turns banning available positions, Vova moves first. During each turn one of the guys bans exactly one of the remaining positions. Banned positions cannot be used by both Vova and Lesha. They continue to make moves until there are only two possible positions remaining (thus, the total number of moves will be n - 2). After that Vova's character takes the position with the lesser coordinate and Lesha's character takes the position with the bigger coordinate and the guys start fighting.

Vova and Lesha are already tired by the game of choosing positions, as they need to play it before every fight, so they asked you (the developer of the The Ancient Papyri: Swordsink) to write a module that would automatically determine the distance at which the warrior and the archer will start fighting if both Vova and Lesha play optimally.

Input

The first line on the input contains a single integer n (2 ≤ n ≤ 200 000, n is even) — the number of positions available initially. The second line contains n distinct integers x1, x2, ..., xn (0 ≤ xi ≤ 109), giving the coordinates of the corresponding positions.

Output

Print the distance between the warrior and the archer at the beginning of the fight, provided that both Vova and Lesha play optimally.

Examples

Input

6
0 1 3 7 15 31


Output

7


Input

2
73 37


Output

36

Note

In the first sample one of the optimum behavior of the players looks like that:

  1. Vova bans the position at coordinate 15; 
  2. Lesha bans the position at coordinate 3; 
  3. Vova bans the position at coordinate 31; 
  4. Lesha bans the position at coordinate 1. 



After these actions only positions 0 and 7 will remain, and the distance between them is equal to 7.

In the second sample there are only two possible positions, so there will be no bans.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author IgorKoval
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		OutputWriter out = new OutputWriter(outputStream);
		TaskA solver = new TaskA();
		solver.solve(1, in, out);
		out.close();
	}

	static class TaskA {
		public void solve(int testNumber, InputReader in, OutputWriter out) {
			int n;
			int[] a;

			n = in.readInt();
			a = IOUtils.readIntArray(in, n);
			ArrayUtils.sort(a, IntComparator.DEFAULT);
			int length = n - (n - 2 + 1) / 2;
			int ans = Integer.MAX_VALUE;
			for (int i = 0; i + length <= n; i++) {
				ans = Math.min(ans, a[i + length - 1] - a[i]);
//			out.printLine(i, i + length - 1);
			}
			out.printLine(ans);
		}

	}

	static class ArrayUtils {
		public static int[] sort(int[] array, IntComparator comparator) {
			return sort(array, 0, array.length, comparator);
		}

		public static int[] sort(int[] array, int from, int to, IntComparator comparator) {
			if (from == 0 && to == array.length)
				new IntArray(array).inPlaceSort(comparator);
			else
				new IntArray(array).subList(from, to).inPlaceSort(comparator);
			return array;
		}

	}

	static interface IntComparator {
		public static final IntComparator DEFAULT = new IntComparator() {
			public int compare(int first, int second) {
				if (first < second)
					return -1;
				if (first > second)
					return 1;
				return 0;
			}
		};

		public int compare(int first, int second);

	}

	static interface IntIterator {
		public int value();

		public void advance();

		public boolean isValid();

	}

	static class IntArray extends IntList {
		private final int[] array;

		public IntArray(int[] array) {
			this.array = array;
		}

		public IntArray(IntCollection collection) {
			array = new int[collection.size()];
			int i = 0;
			for (IntIterator iterator = collection.iterator(); iterator.isValid(); iterator.advance())
				array[i++] = iterator.value();
		}


		public int get(int index) {
			return array[index];
		}


		public void set(int index, int value) {
			array[index] = value;
		}


		public int size() {
			return array.length;
		}

	}

	static abstract class IntList extends IntCollection implements Comparable<IntList> {
		private static final int INSERTION_THRESHOLD = 16;

		public abstract int get(int index);

		public abstract void set(int index, int value);


		public IntIterator iterator() {
			return new IntIterator() {
				private int size = size();
				private int index = 0;

				public int value() throws NoSuchElementException {
					if (!isValid())
						throw new NoSuchElementException();
					return get(index);
				}

				public void advance() throws NoSuchElementException {
					if (!isValid())
						throw new NoSuchElementException();
					index++;
				}

				public boolean isValid() {
					return index < size;
				}
			};
		}

		public IntList subList(final int from, final int to) {
			return new SubList(from, to);
		}

		private void swap(int first, int second) {
			if (first == second)
				return;
			int temp = get(first);
			set(first, get(second));
			set(second, temp);
		}

		public IntSortedList inPlaceSort(IntComparator comparator) {
			quickSort(0, size() - 1, (Integer.bitCount(Integer.highestOneBit(size()) - 1) * 5) >> 1, comparator);
			return new IntSortedArray(this, comparator);
		}

		private void quickSort(int from, int to, int remaining, IntComparator comparator) {
			if (to - from < INSERTION_THRESHOLD) {
				insertionSort(from, to, comparator);
				return;
			}
			if (remaining == 0) {
				heapSort(from, to, comparator);
				return;
			}
			remaining--;
			int pivotIndex = (from + to) >> 1;
			int pivot = get(pivotIndex);
			swap(pivotIndex, to);
			int storeIndex = from;
			int equalIndex = to;
			for (int i = from; i < equalIndex; i++) {
				int value = comparator.compare(get(i), pivot);
				if (value < 0)
					swap(storeIndex++, i);
				else if (value == 0)
					swap(--equalIndex, i--);
			}
			quickSort(from, storeIndex - 1, remaining, comparator);
			for (int i = equalIndex; i <= to; i++)
				swap(storeIndex++, i);
			quickSort(storeIndex, to, remaining, comparator);
		}

		private void heapSort(int from, int to, IntComparator comparator) {
			for (int i = (to + from - 1) >> 1; i >= from; i--)
				siftDown(i, to, comparator, from);
			for (int i = to; i > from; i--) {
				swap(from, i);
				siftDown(from, i - 1, comparator, from);
			}
		}

		private void siftDown(int start, int end, IntComparator comparator, int delta) {
			int value = get(start);
			while (true) {
				int child = ((start - delta) << 1) + 1 + delta;
				if (child > end)
					return;
				int childValue = get(child);
				if (child + 1 <= end) {
					int otherValue = get(child + 1);
					if (comparator.compare(otherValue, childValue) > 0) {
						child++;
						childValue = otherValue;
					}
				}
				if (comparator.compare(value, childValue) >= 0)
					return;
				swap(start, child);
				start = child;
			}
		}

		private void insertionSort(int from, int to, IntComparator comparator) {
			for (int i = from + 1; i <= to; i++) {
				int value = get(i);
				for (int j = i - 1; j >= from; j--) {
					if (comparator.compare(get(j), value) <= 0)
						break;
					swap(j, j + 1);
				}
			}
		}

		public int hashCode() {
			int hashCode = 1;
			for (IntIterator i = iterator(); i.isValid(); i.advance())
				hashCode = 31 * hashCode + i.value();
			return hashCode;
		}


		public boolean equals(Object obj) {
			if (!(obj instanceof IntList))
				return false;
			IntList list = (IntList) obj;
			if (list.size() != size())
				return false;
			IntIterator i = iterator();
			IntIterator j = list.iterator();
			while (i.isValid()) {
				if (i.value() != j.value())
					return false;
				i.advance();
				j.advance();
			}
			return true;
		}

		public int compareTo(IntList o) {
			IntIterator i = iterator();
			IntIterator j = o.iterator();
			while (true) {
				if (i.isValid()) {
					if (j.isValid()) {
						if (i.value() != j.value()) {
							if (i.value() < j.value())
								return -1;
							else
								return 1;
						}
					} else
						return 1;
				} else {
					if (j.isValid())
						return -1;
					else
						return 0;
				}
				i.advance();
				j.advance();
			}
		}

		private class SubList extends IntList {
			private final int to;
			private final int from;
			private int size;

			public SubList(int from, int to) {
				this.to = to;
				this.from = from;
				size = to - from;
			}


			public int get(int index) {
				if (index < 0 || index >= size)
					throw new IndexOutOfBoundsException();
				return IntList.this.get(index + from);
			}


			public void set(int index, int value) {
				if (index < 0 || index >= size)
					throw new IndexOutOfBoundsException();
				IntList.this.set(index + from, value);
			}


			public int size() {
				return size;
			}

		}

	}

	static class OutputWriter {
		private final PrintWriter writer;

		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}

		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}

		public void close() {
			writer.close();
		}

		public void printLine(int i) {
			writer.println(i);
		}

	}

	static class IOUtils {
		public static int[] readIntArray(InputReader in, int size) {
			int[] array = new int[size];
			for (int i = 0; i < size; i++)
				array[i] = in.readInt();
			return array;
		}

	}

	static class IntSortedArray extends IntSortedList {
		private final int[] array;

		public IntSortedArray(int[] array) {
			this(array, IntComparator.DEFAULT);
		}

		public IntSortedArray(IntCollection collection) {
			this(collection, IntComparator.DEFAULT);
		}

		public IntSortedArray(int[] array, IntComparator comparator) {
			super(comparator);
			this.array = array;
			ensureSorted();
		}

		public IntSortedArray(IntCollection collection, IntComparator comparator) {
			super(comparator);
			array = new int[collection.size()];
			int i = 0;
			for (IntIterator iterator = collection.iterator(); iterator.isValid(); iterator.advance())
				array[i++] = iterator.value();
			ensureSorted();
		}


		public int get(int index) {
			return array[index];
		}


		public int size() {
			return array.length;
		}

	}

	static abstract class IntCollection {
		public abstract IntIterator iterator();

		public abstract int size();

	}

	static abstract class IntSortedList extends IntList {
		protected final IntComparator comparator;

		protected IntSortedList(IntComparator comparator) {
			this.comparator = comparator;
		}


		public void set(int index, int value) {
			throw new UnsupportedOperationException();
		}


		public IntSortedList inPlaceSort(IntComparator comparator) {
			if (comparator == this.comparator)
				return this;
			throw new UnsupportedOperationException();
		}

		protected void ensureSorted() {
			int size = size();
			if (size == 0)
				return;
			int last = get(0);
			for (int i = 1; i < size; i++) {
				int current = get(i);
				if (comparator.compare(last, current) > 0)
					throw new IllegalArgumentException();
				last = current;
			}
		}


		public IntSortedList subList(final int from, final int to) {
			return new IntSortedList(comparator) {
				private int size = to - from;


				public int get(int index) {
					if (index < 0 || index >= size)
						throw new IndexOutOfBoundsException();
					return IntSortedList.this.get(index + from);
				}


				public int size() {
					return size;
				}
			};
		}

	}

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int readInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return isWhitespace(c);
		}

		public static boolean isWhitespace(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);

		}

	}
}