(lcd.*)

Vinh mới mua một màn hình LCD của công ty công nghệ StarTech mới thiết kế có độ phân giải màu sắc gồm \(M\) mức màu, đó là mức 1, mức 2, ..., mức \(M\). Thiết bị điều khiển của màn hình gồm 2 nút bấm điều khiển. Nút bấm thứ nhất được gọi là nút “Inc”. Khi bấm vào nút này, nếu màn hình đang ở mức màu \(i\ (i\ < \ M)\) thì sẽ chuyển lên mức màu \(i\ + \ 1\), nếu \(i\ = \ M\) thì sẽ chuyển về mức màu 1. Nút bấm thứ 2 được gọi là nút “favorite”, khi bấm vào nút này mức màu của màn hình sẽ chuyển về mức \(X\), với \(X\) là một thông số được thiết lập trước.

Màn hình thì rất đẹp, chiếc điều khiển cũng rất đẹp. Vinh muốn thử chiếc điều khiển và kiểm tra các mức màu của màn hình. Vinh đưa ra một dãy mức màu \(A_{1},A_{2}\ldots,A_{N}\) (1 \(\leq A_{i} \leq M\), \(A_{i}
eq A_{i + 1}\)) và sẽ điều khiển để màn hình từ mức \(A_{i}\) chuyển sang mức \(A_{i + 1}\) (\(i\ = \ 1,\ 2,\ ...,\ N\ - \ 1\)) bằng cách bấm vào các nút bấm. Ban đầu màn hình ở mức màu \(A_{1}\). Gọi \(S(X)\) là tổng số lần bấm ít nhất để chuyển từ mức màu \(A_{1}\) sang \(A_{2}\), từ \(A_{2}\) sang \(A_{3}\), ..., từ \(A_{N - 1}\) sang \(A_{N}\) ứng với thông số thiết lập là mức \(X\).

Yêu cầu: Tìm giá trị nhỏ nhất của \(S(X)\) khi \(X\) thay đổi từ 1 đến \(M\).

Dữ liệu vào:

• Dòng thứ nhất ghi 2 số nguyên dương \(N\) và \(M\).

• Dòng thứ hai ghi \(N\) số nguyên \(A_{1},A_{2}\ldots,A_{N}\) (1 \(\leq A_{i} \leq M\)).

Kết quả: gồm một số nguyên là giá trị nhỏ nhất của \(S(X)\) khi \(X\) thay đổi từ 1 đến \(M\).

Ví dụ:

Giới hạn:

• Có 25% số test ứng với 2 \(\leq N,M \leq 10^{5}\); 1 \(\leq A_{1} < A_{2} < \ldots < A_{N} \leq M\);

• Có 25% số test ứng với 2 \(\leq N,M \leq 10^{3}\);

• Có 50% số test ứng với 2 \(\leq N,M \leq 10^{5}\).