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.*;
import java.util.*;

public class Main {
    private boolean eof;
    private BufferedReader br;
    private StringTokenizer st;
    private static PrintWriter out;

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    private String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return "-1";
            }
        }
        return st.nextToken();
    }

    private int nextInt() {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() {
        return Double.parseDouble(nextToken());
    }

    private String nextLine() throws IOException {
        return br.readLine();
    }

    private ArrayList<Integer> nextIntArray(int size) {
        ArrayList<Integer> input = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            input.add(nextInt());
        }
        return input;
    }

    private void run() throws IOException {
        InputStream input = System.in;
        PrintStream output = System.out;
        try {
            File f = new File("a.in");
            if (f.exists() && f.canRead()) {
                input = new FileInputStream(f);
                output = new PrintStream("a.out");
            }
        } catch (Throwable ignored) {
        }
        br = new BufferedReader(new InputStreamReader(input));
        out = new PrintWriter(new PrintWriter(output));
        solve();
        br.close();
        out.close();
    }

    private static int n,m;
    private static ArrayList<Integer> a;

    private static boolean check(int x) {
        int prev = 0;
        for (int i = 0; i < n; i++) {
            if (a.get(i) + x >= m) {
                if (prev > (a.get(i) + x) % m && prev <= a.get(i)) {
                    prev = a.get(i);
                }
            } else {
                if (prev <= a.get(i) + x) {
                    prev = Math.max(prev, a.get(i));
                } else {
                    return false;
                }
            }
        }
        return true;
    }

    private void solve() {
        n = nextInt();
        m = nextInt();
        a = nextIntArray(n);

        int l = -1, r = m + 1;
        while (r - l > 1) {
            int mid = (l + r) / 2;
            boolean f = check(mid);
//            out.println("CHECK:" + mid + " " + f);
            if (f) {
                r = mid;
            } else {
                l = mid;
            }
        }
        out.println(l + 1);
    }

    public static int gcd(int a, int b) {
        while (b > 0) {
            a %= b;
            int c = a;
            a = b;
            b = c;
        }
        return a;
    }

    private static Random rnd = new Random();

    public static class Node {
        public int key;
        public int prior;
        public int cnt;
        public boolean pushing;
        public Node left, right;

        Node(int key, int index) {
            this.key = key;
            this.prior = rnd.nextInt();
            left = right = null;
            this.cnt = 1;
            this.pushing = false;
        }
    }

    public static int getCnt(Node t) {
        return t == null ? 0 : t.cnt;
    }


    public static void update(Node t) {
        if (t != null) {
            t.cnt = 1 + getCnt(t.left) + getCnt(t.right);
        }
    }

    public static void push(Node t) {
        if (t != null && t.pushing) {

            t.pushing = false;
        }
    }

    public static void pushAll(Node t) {
        if (t != null) {
            push(t);
            if (t.left != null) {
                pushAll(t.left);
            }
            if (t.right != null) {
                pushAll(t.right);
            }
        }
    }

    // [0,K),[K,N)
    public static Pair<Node, Node> split(Node t, int key) {
        if (t == null) return new Pair<>(null, null);
        push(t);
        if (key > t.key) {
            Pair<Node, Node> p = split(t.right, key);
            t.right = p.first;
            update(t);
            return new Pair<>(t, p.second);
        } else {
            Pair<Node, Node> p = split(t.left, key);
            t.left = p.second;
            update(t);
            return new Pair<>(p.first, t);
        }
    }

    //SPLIT ПО НЕЯВНОМУ КЛЮЧУ
    // [0,K),[K,N)
    public static Pair<Node, Node> split(Node t, int key, int add) {
        if (t == null) return new Pair<>(null, null);
        push(t);
        int curKey = add + getCnt(t.left);
        if (key > curKey) { //идем в правое поддерево
            Pair<Node, Node> p = split(t.right, key, curKey + 1);
            t.right = p.first;
            update(t);
            return new Pair<>(t, p.second);
        } else { //идем в левое поддерево
            Pair<Node, Node> p = split(t.left, key, add);
            t.left = p.second;
            update(t);
            return new Pair<>(p.first, t);
        }
    }

    //Все ключи в первом дереве должны быть меньше ключей во втором
    public static Node merge(Node t1, Node t2) {
        push(t1);
        push(t2);
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        if (t1.prior > t2.prior) {
            t1.right = merge(t1.right, t2);
            update(t1);
            return t1;
        } else {
            t2.left = merge(t1, t2.left);
            update(t2);
            return t2;
        }
    }

//    public static Node insert(Node t, Node newNode) {
//        push(t);
//        if (t == null) {
//            t = newNode;
//        } else if (newNode.prior > t.prior) {
//            Pair<Node, Node> p = split(t, newNode.key);
//            newNode.left = p.first;
//            newNode.right = p.second;
//            t = newNode;
//        } else {
//            if (newNode.key < t.key) {
//                t.left = insert(t.left, newNode);
//            } else {
//                t.right = insert(t.right, newNode);
//            }
//        }
//        update(t);
//        return t;
//    }

    public static Node insert(Node t, Node newNode) {
        push(t);
        if (t == null) {
            t = newNode;
        } else {
            Pair<Node, Node> p = split(t, newNode.key, 0);
            t = merge(p.first, newNode);
            t = merge(t, p.second);
        }
        update(t);
        return t;
    }

    //Объединяет 2 разных дерева
    public static Node unite(Node t1, Node t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        push(t1);
        push(t2);
        if (t1.prior < t2.prior) {
            Node c = t1;
            t1 = t2;
            t2 = c;
        }
        Pair<Node, Node> split1 = split(t2, t1.key);
        t1.left = unite(t1.left, split1.first);
        t1.right = unite(t1.right, split1.second);
        return t1;
    }

    public static Node remove(Node t, int key) {
        if (t == null) return null;
        if (t.key == key) {
            t = merge(t.left, t.right);
        } else {
            if (key < t.key) {
                t.left = remove(t.left, key);
            } else {
                t.right = remove(t.right, key);
            }
        }
        update(t);
        return t;
    }

    public static Node find(Node t, int key) {
        push(t);
        if (t == null) return null;
        if (t.key == key) return t;
        if (t.key < key) {
            return find(t.right, key);
        } else {
            return find(t.left, key);
        }
    }

    public static Node get(Node t, int key, int add) {
        push(t);
        if (t == null) return null;
        int curKey = add + getCnt(t.left);
        if (curKey == key) return t;
        if (key > curKey) { //идем в правое поддерево
            return get(t.right, key, curKey + 1);
        } else {
            return get(t.left, key, add);
        }
    }

    /**
     * Вырезает отрезок от i до j и вставляет в позицию k нового массива
     * (при k = 0 вставляет вначало)
     *
     * @param t Корень дерева
     * @param i Начало отрезка (включительно)
     * @param j Конец отрезка (включительно)
     * @param k Позиция вставки
     * @return Новое дерево
     */
    public static Node replaceSegment(Node t, int i, int j, int k) {
        //Вырезаем отрезок и склеиваем
        Pair<Node, Node> split1 = split(t, i, 0);
        Pair<Node, Node> split2 = split(split1.second, j - i + 1, 0);
        Node merge1 = merge(split1.first, split2.second);
        Node removedSegment = split2.first;

//      out.println("Array without removed:" + getString(merge1));
//      out.println("Removed Segment:" + getString(removedSegment));

        //разделяем и вставляем
        Pair<Node, Node> split3 = split(merge1, k, 0);
        Node merge2 = merge(split3.first, removedSegment);
        Node merge3 = merge(merge2, split3.second);

        return merge3;
    }

    public static StringBuilder getKeysString(Node t) {
        if (t == null) return new StringBuilder();
        StringBuilder ans = new StringBuilder();
        if (t.left != null) ans.append(getKeysString(t.left));
        ans.append(t.key);
        ans.append(" ");
        if (t.right != null) ans.append(getKeysString(t.right));
        return ans;
    }

    public static class Pair<F, S> {
        public F first;
        public S second;

        Pair(F first, S second) {
            this.first = first;
            this.second = second;
        }

//        @Override
//        public int compareTo(Object o) {
//            return first.compareTo(((Pair)o).first);
//        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Main.Pair)) {
                return false;
            }
            Main.Pair<?, ?> p = (Main.Pair<?, ?>) o;
            return Objects.equals(p.first, first) && Objects.equals(p.second, second);
        }

        @Override
        public int hashCode() {
            return (first == null ? 0 : first.hashCode()) ^ (second == null ? 0 : second.hashCode());
        }
    }
}