Tăng theo modulo

Cho một dãy $N$ số nguyên $A_1,A_2,\dots ,A_N$, mỗi số nằm trong đoạn từ $0$ đến $M-1$.

Trong một thao tác, bạn được chọn một tập chỉ số bất kỳ (có thể rỗng) $i_1<i_2<\dots <i_k$, rồi thay đồng thời mỗi $A_{i_j}$ thành $(A_{i_j}+1)modM$. Giá trị $M$ là cố định cho mọi thao tác.

Nói cách khác, mỗi thao tác cho phép tăng thêm $1$ theo modulo $M$ cho bao nhiêu phần tử tuỳ ý, kể cả tất cả.

Hãy tìm số thao tác ít nhất cần dùng để dãy trở thành không giảm, tức là $A_1\le A_2\le \dots \le A_N$. Nếu dãy đã không giảm sẵn thì đáp án là $0$. Luôn tồn tại cách làm với đủ số thao tác.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $M$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\dots ,A_N$.

Dữ liệu ra

Một dòng chứa một số nguyên: số thao tác ít nhất cần thực hiện.

Ràng buộc

• $1\le N,M\le 300000$
• $0\le A_i<M$

Ví dụ