306251: CF1168A. Increasing by Modulo
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Increasing by Modulo
题意翻译
给出 $n,m$,以及 $m$ 个数 $a_1,a_2,\ldots,a_n$。 每次选一个数 $k$ 及 $k$ 个数 $1\leq b_1\lt b_2\lt\ldots\lt b_k\leq n$,并将所有 $a_{b_i}$ 变成 $(a_{b_i}+1)\bmod m$,求最少操作数,使 $a$ 数组不下降。题目描述
Toad 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.输入输出格式
输入格式
The 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.
输出格式
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.
输入输出样例
输入样例 #1
5 3
0 0 0 1 2
输出样例 #1
0
输入样例 #2
5 7
0 6 1 3 2
输出样例 #2
1