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.
//package sept;

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



public class TimePass implements Runnable {
    InputStream is;
    PrintWriter out;
    String INPUT = "100000 300 300";
    //boolean debug=false;
    boolean debug=true;
    static long mod=998244353;
    static long mod2=1000000007;
    
    static int[][] arr= new int[][]{{2,-1},{2,1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
    static HashMap<Long,Integer> map;
    void solve() throws IOException
    {
    	int n=ni(),m=ni();
    	int[] a=na(n);
    	int low=0,high=300005;
    	
    	while(low<high)
    	{
    		int mid=(low+high)/2;
    		if(check(a,mid,n,m))
    		{
    			high=mid;
    		}
    		else
    		{
    			low=mid+1;
    		}
    	}
    	out.println(high);
	}
    
    boolean check(int[] a,int d,int n,int m)
    {
    	int prev=m-1;
    	for(int i=n-1;i>=0;i--)
    	{
    		int curr=a[i];
    		if(curr<prev)
    		{
    			prev=Math.min(prev, (curr+d>=m)?(m-1):(curr+d));
    		}
    		else if(curr>prev)
    		{
    			if(curr+d<m)return false;
    			prev=Math.min(prev,(curr+d)%m);
    		}
    	}
    	return true;
    }
    
    public void round1()
    {
    	int n=ni(),a=ni(),b=ni(),x=ni(),y=ni();
    	map=new HashMap<>();
    	for(int i=0;i<8;i++)
    	{
    		for(int j=0;j<8;j++)
    		{
    			int cnt=0;
    			for(int k=0;k<8;k++)
    			{
    				int cx=i+arr[k][0];
    				int cy=j+arr[k][1];
    				if(cx>=0 && cx<8 && cy>=0 && cy<8)
    				{
    					cnt++;
    				}
    			}
    			map.put(fnc(i,j), cnt);
    		}
    	}
    	dp2=new long[8][8][100001];
    	for(int i=0;i<8;i++)
    		for(int j=0;j<8;j++)
    			Arrays.fill(dp2[i][j], -1);
    	
    	out.println(ways(a,b,x,y,n));
    }
    
    public long fnc(int a,int b)
    {
    	return a+b*mod2;
    }
    
    static long[][][] dp2;
    
    public long ways(int a,int b,int x,int y,int n)
    {
    	if(n==0)
    	{
    		if(a==x && b==y)return 1;
    		else return 0;
    	}
    	if(dp2[x][y][n]!=-1)return dp2[x][y][n];
    	long sum=0;
    	for(int i=0;i<8;i++)
    	{
    		int cx=x+arr[i][0];
    		int cy=y+arr[i][1];
    		if(cx>=0 && cx<=7 && cy>=0 && cy<=7)
    		{
    			sum=(sum+(ways(a,b,cx,cy,n-1)*inv(map.get(fnc(cx,cy)),(int)mod2))%mod2)%mod2;
    		}
    	}
    	dp2[x][y][n]=sum;
    	return sum;
    }
    
    static long[][] dp;
    
    public long comp(int[] a,int st,int n,int m,int k)
    {
    	if(m==0)return 0;
    	long sum=0,max=0;
    	if(dp[st][m]!=-1)return dp[st][m];
    	for(int i=st;i<st+k;i++)
    	{
    		sum+=a[i];
    	}
    	long maxsum=sum;
    	max=sum+comp(a,st+k,n,m-1,k);
    	for(int i=st+k;i<n-(m-1)*k;i++)
    	{
    		sum+=a[i];
    		sum-=a[i-k];
    		maxsum=Math.max(maxsum, sum);
    		max=Math.max(max, maxsum+comp(a,i+1,n,m-1,k));
    	}
    	dp[st][m]=max;
    	return max;
    }
    
    static class DSets
    {
        int[] p;
        int[] r;
        int[] s;
        int size;
        int max_component;
        
        public DSets(int n)
        {
            s=new int[n+1];
            r=new int[n+1];
            p=new int[n+1];
            for(int i=1;i<=n;i++)
            {
                r[i]=0;
                p[i]=i;
                s[i]=1;
            }
            this.size=n+1;
        }
        
        public int find(int x)
        {
            if(x != p[x]){
                p[x] = find(p[x]) ;
            }
            return p[x] ;
        }
        
        public boolean unionBySize(int x,int y)
        {
            int rx , ry ;
            rx = find(x) ;
            ry = find(y) ;
            if(rx != ry)
            {
                if(r[rx] < r[ry])
                {
                    p[rx] = ry ;
                    s[ry] += s[rx] ;
                    max_component = Math.max(max_component,s[ry]) ;
                }
                else
                {
                    p[ry] = rx ;
                    s[rx] += s[ry] ;
                    max_component = Math.max(max_component,s[rx]) ;
                }
                if(r[rx] == r[ry])
                {
                    r[rx] ++;
                }
                return true ;
            }
            return false ;
        }
    }
    
	static Pair[][] packU(int n,int[] from,Pair[] to)
	{
		Pair[][] g=new Pair[n][];
		int[] p=new int[n];
		for(int f:from)
		{
			p[f]++;
		}
		int m=from.length;
		for(int i=0;i<n;i++)
		{
			g[i]=new Pair[p[i]];
		}
		for(int i=0;i<m;i++)
		{
			g[from[i]][--p[from[i]]]=to[i];
		}
		return g;
	}
    
	static int[][] packD(int n,int[] from,int[] to)
	{
		int[][] g=new int[n][];
		int[] p=new int[n];
		for(int f:from)
		{
			p[f]++;
		}
		int m=from.length;
		for(int i=0;i<n;i++)
		{
			g[i]=new int[p[i]];
		}
		for(int i=0;i<m;i++)
		{
			g[from[i]][--p[from[i]]]=to[i];
		}
		return g;
	}
	    
    static class Pair
    {
    	long a,b,c;
    	//int a,b,c;
        public Pair(long a,long b)
        {
            this.a=a;
            this.b=b;
            //this.ind=ind;
        }
    }
    
    static long lcm(int a,int b)
    {
        long val=a;
        val*=b;
        return (val/gcd(a,b));
    }
    
    static long gcd(long a,long b)
    {
        if(a==0)return b;
        return gcd(b%a,a);
    }
    
    static int pow(int a, int b, int p)
    {
        long ans = 1, base = a;
        while (b!=0)
        {
            if ((b & 1)!=0)
            {
                ans *= base;
                ans%= p;
            }
            base *= base;
            base%= p;
            b >>= 1;
        }
        return (int)ans;
    }

    static int inv(int x, int p)
    {
        return pow(x, p - 2, p);
    }
    
    public static long[] radixSort(long[] f){ return radixSort(f, f.length); }
	public static long[] radixSort(long[] f, int n)
	{
		long[] to = new long[n];
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>16&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>16&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>32&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>32&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>48&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>48&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		return f;
	}
    
    public void run()
    {
        if(debug)oj=true;
        is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        try {
			solve();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
        out.flush();
        tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception {new Thread(null,new TimePass(),"Main",1<<26).start();}
    
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
    private void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}
