Toad Zitz has an array of integers, each integer is between 0 and m-1 inclusive. The integers are a_1, a_2, …, a_n.

In one operation Zitz can choose an integer k and k indices i_1, i_2, …, i_k such that 1 ≤ i_1 < i_2 < … < i_k ≤ n. He should then change a_{i_j} to ((a_{i_j}+1) mod m) for each chosen integer i_j. The integer m is fixed for all operations and indices.

Here x mod y denotes the remainder of the division of x by y.

Zitz wants to make his array non-decreasing with the minimum number of such operations. Find this minimum number of operations.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 300 000) — the number of integers in the array and the parameter m.

The next line contains n space-separated integers a_1, a_2, …, a_n (0 ≤ a_i < m) — the given array.

Output

Output one integer: the minimum number of described operations Zitz needs to make his array non-decreasing. If no operations required, print 0.

It is easy to see that with enough operations Zitz can always make his array non-decreasing.

Examples

Input


5 3
0 0 0 1 2


Output


0


Input


5 7
0 6 1 3 2


Output


1

Note

In the first example, the array is already non-decreasing, so the answer is 0.

In the second example, you can choose k=2, i_1 = 2, i_2 = 5, the array becomes [0,0,1,3,3]. It is non-decreasing, so the answer is 1.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.TreeMap;
import java.util.TreeSet;

public class Solution1 implements Runnable {
	static final long MAX = 464897L;

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
		private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		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 String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

		public int nextInt() {
			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 long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long 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 double nextDouble() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') {
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, nextInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') {
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) {
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, nextInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}

		public String readString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));

			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public String next() {
			return readString();
		}

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

	public static void main(String args[]) throws Exception {
		new Thread(null, new Solution1(), "Solution1", 1 << 26).start();
	}

	static long gcd(long a, long b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

	static long lcm(long a, long b) {
		return (a * b) / gcd(a, b);
	}

	int maxn = 1000005;
	long MOD = 998244353;
	long prime = 29;
	ArrayList<Integer> adj[];
	TreeMap<Long, Long> tmap = new TreeMap();
	int[] val;
	int[] ans;

	public void run() {
		InputReader sc = new InputReader(System.in);
		PrintWriter w = new PrintWriter(System.out);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0;i < n;i++) {
			arr[i]=  sc.nextInt();
		}
		int l = 0;
		int r = m;
		int ans = n;
		while(l <= r) {
			int mid = (l + r)/2;
			if(check(mid,arr,m)) {
				r = mid - 1;
				ans = mid;
			}else {
				l = mid + 1;
			}
		}
		w.println(ans);
		w.close();
	}
	boolean check(int mid,int[] arr,int m) {
		int glbmin = 0;
		for(int i = 0;i < arr.length;i++) {
			if(arr[i] <= glbmin) {
				if(glbmin - arr[i] > mid) {
					return false;
				}
			}else {
				if(glbmin + m - arr[i] <= mid) {
					
				}else {
					glbmin = arr[i];
				}
			}
		}
		return true;
	}
	boolean fun(int one,int two,Pair[] p) {
		for(int i = 0;i < p.length;i++) {
			TreeSet<Integer> tset = new TreeSet();
			tset.add(one);
			tset.add(two);
			tset.add(p[i].a);
			tset.add(p[i].b);
			if(tset.size() == 4) {
				return false;
			}
		}
		return true;
	}
	static long power(long a, long b, long mod) {
		long ans = 1;
		a = a % mod;
		while (b != 0) {
			if (b % 2 == 1) {
				ans = (ans * a) % mod;
			}
			a = (a * a) % mod;
			b = b / 2;
		}
		return ans;
	}

	class Pair implements Comparable<Pair> {
		int a;
		int b;
		int c;

		Pair(int a, int b, int c) {
			this.b = b;
			this.a = a;
			this.c = c;
		}

		public boolean equals(Object o) {
			Pair p = (Pair) o;
			return this.a == p.a && this.b == this.b;
		}

		public int hashCode() {
			return Long.hashCode(a) * 27 + Long.hashCode(b) * 31;
		}
		public int compareTo(Pair p) {
			return Long.compare(this.b, p.b);
		}
	}

	class Pair2 implements Comparable<Pair2> {
		int a;
		int b;
		int c;

		Pair2(int a, int b, int c) {
			this.b = b;
			this.a = a;
			this.c = c;
		}

		public boolean equals(Object o) {
			Pair p = (Pair) o;
			return this.a == p.a && this.b == this.b;
		}

		public int hashCode() {
			return Long.hashCode(a) * 27 + Long.hashCode(b) * 31;
		}

		public int compareTo(Pair2 p) {
			return Long.compare(p.a, this.a);
		}
	}
}