A. Increasing by Modulotime limit per test2.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputToad Zitz has an array of integers, each integer is between 0 and m-1 inclusive. The integers are a_1, a_2, \ldots, a_n.In one operation Zitz can choose an integer k and k indices i_1, i_2, \ldots, i_k such that 1 \leq i_1 < i_2 < \ldots < i_k \leq n. He should then change a_{i_j} to ((a_{i_j}+1) \bmod m) for each chosen integer i_j. The integer m is fixed for all operations and indices.Here x \bmod 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.InputThe first line contains two integers n and m (1 \leq n, m \leq 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, \ldots, a_n (0 \leq a_i < m) — the given array.OutputOutput 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.ExamplesInput
5 3
0 0 0 1 2
Output
0
Input
5 7
0 6 1 3 2
Output
1
NoteIn 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.
5 3
0 0 0 1 2

0 
['binary search', 'greedy', '*1700']