Problem:


Score : 700 points

Problem Statement

Snuke is buying a lamp.
The light of the lamp can be adjusted to m levels of brightness, represented by integers from 1 through m, by the two buttons on the remote control.

The first button is a "forward" button. When this button is pressed, the brightness level is increased by 1, except when the brightness level is m, in which case the brightness level becomes 1.

The second button is a "favorite" button. When this button is pressed, the brightness level becomes the favorite brightness level x, which is set when the lamp is purchased.

Snuke is thinking of setting the favorite brightness level x so that he can efficiently adjust the brightness.
He is planning to change the brightness n-1 times. In the i-th change, the brightness level is changed from a_i to a_{i+1}. The initial brightness level is a_1.
Find the number of times Snuke needs to press the buttons when x is set to minimize this number.

Constraints

2 \leq n,m \leq 10^5

1 \leq a_i\leq m

a_i \neq a_{i+1}

n, m and a_i are integers.

Input

Input is given from Standard Input in the following format:

n m
a_1 a_2 … a_n

Output

Print the minimum number of times Snuke needs to press the buttons.

Sample Input 1

4 6
1 5 1 4

Sample Output 1

5

When the favorite brightness level is set to 1, 2, 3, 4, 5 and 6, Snuke needs to press the buttons 8, 9, 7, 5, 6 and 9 times, respectively.
Thus, Snuke should set the favorite brightness level to 4.
In this case, the brightness is adjusted as follows:

In the first change, press the favorite button once, then press the forward button once.

In the second change, press the forward button twice.

In the third change, press the favorite button once.

Sample Input 2

10 10
10 9 8 7 6 5 4 3 2 1

Sample Output 2

45



Sample input:
4 6
1 5 1 4


Sample output:
5

Submission status: Accepted

Solution code:
"""
a(x-p) + b (p <= x <= q) の2階階差をとり、imos配列に加える
復元はaccumulateでやる
"""
def kaisa2_of_tousa(a,b,p,q,imos,n):
    if p > q: return
    imos[p] += b
    if p+1 < n: imos[p+1] += a-b
    y = a*(q-p)+b
    if q+1 < n: imos[q+1] += -y-a
    if q+2 < n: imos[q+2] += y

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m,*a = map(int,read().split())

imos = [0]*(2*m+1)
ans = 0
for p,q in zip(a,a[1:]):
    if p > q: q += m
    ans += q-p
    kaisa2_of_tousa(-1,0,p+1,q,imos,2*m+1)

from itertools import accumulate as acc
res = list(acc(acc(imos)))


v = 0
for i in range(1,m+1):
    w = res[i]+res[i+m]
    v = min(v,w)
    #print(w)

#print(ans)
print(ans+v)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [int(x) for x in input().split()]
ps = [0]*(m+2)  # 0,1,2,...,m,m+1

for i in range(n-1):
    if a[i] < a[i+1]:
        ps[a[i]+1] += 1
        ps[a[i+1]] -= 1
    else:
        ps[0] += 1
        ps[a[i+1]] -= 1
        ps[a[i]+1] += 1
        ps[m+1] -= 1

aps = [0]
for x in ps[:-1]:
    aps.append(aps[-1]+x)
aps = aps[2:]


def dist(src, tar):
    return (m+tar-src) % m


freq = [0]*m
for i, x in enumerate(a):
    if i == 0:
        continue
    freq[x-1] += dist(a[i-1], a[i])-1


ans = [0]*m
for i in range(n-1):
    ans[0] += min(dist(a[i], a[i+1]), 1+dist(1, a[i+1]))

for i in range(1, m):
    ans[i] = ans[i-1] + freq[i-1] - aps[i-1]

print(min(ans))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=list(map(int,input().split()))
imos1=[0]*(m*2+2)
imos2=[0]*(m*2+2)
imos3=[0]*(m*2+2)
for i in range(n-1):
  cost=(m+arr[i+1]-arr[i])%m
  if arr[i]<arr[i+1]:
    imos1[arr[i]]+=cost
    imos1[arr[i]+m]-=cost
    imos2[arr[i]+2]+=-1
    imos2[arr[i+1]+1]+=1
    imos3[arr[i+1]+1]+=cost-1
  else:
    imos1[arr[i]]+=cost
    imos1[arr[i]+m]-=cost
    imos2[arr[i]+2]+=-1
    imos2[arr[i+1]+m+1]+=1
    imos3[arr[i+1]+m+1]+=cost-1
for i in range(1,m*2+2):
  imos2[i]+=imos2[i-1]
for i in range(m*2+2):
  imos1[i]+=imos2[i]
  imos1[i]+=imos3[i]
for i in range(1,m*2+2):
  imos1[i]+=imos1[i-1]
xs=[0]*(m+1)
xs[0]=10**18
for i in range(1,m+1):
  xs[i]=imos1[i]+imos1[m+i]
print(min(xs))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate

n, m = map(int, input().split())
A = list(map(int, input().split()))
L = [0]*(2*m)
B = []
cnt = 0
for i in range(n-1):
  a, b = A[i], A[i+1]
  a -= 1
  b -= 1
  if a < b:
    cnt += b-a
    if b-a == 1:
      continue
    L[a+2] += 1
    L[b+1] += -1
    B.append((b+1, -(b-a-1)))
  else:
    b += m
    cnt += b-a
    if b-a == 1:
      continue
    L[a+2] += 1
    L[b+1] += -1
    B.append((b+1, -(b-a-1)))
L = list(accumulate(L))
for i, b in B:
  L[i] += b
L = list(accumulate(L))
c = 0
for i in range(m):
  c = max(c, L[i]+L[m+i])
ans = cnt - c
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
l=[0]*(m+2)
for i,j in zip(a,a[1:]):
    if j>i+1:
        l[j+1]-=1
        l[i+2]+=1
    elif i>j:
        if i<=m-2:
            l[i+2]+=1
            l[m+1]-=1
            l[1]+=1
            l[j+1]-=1
        else:
            l[i+2-m]+=1
            l[j+1]-=1
from itertools import accumulate
l=list(accumulate(l))
ans=0
l1=0
for i,j in zip(a,a[1:]):
    if j>i:
        ans+=j-i
        l[j+1]-=(j-i-1)
    else:
        l1+=m-i
        ans+=m+j-i
        l[j+1]-=(m+j-i-1)
l[1]=l1
l=list(accumulate(l))
print(ans-max(l[1:m+1]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=[a[i]-1 for i in range(n)]

imos=[0 for i in range(m+1)]
for i in range(0,n-1):
    s,g=a[i],a[i+1]
    val=(g-s)%m
    if val>1:
        s=(s+2)%m
        if s>g:
            imos[s]+=-1
            imos[m]+=1
            imos[0]+=-1
            imos[g+1]+=1
        else:
            imos[s]+=-1
            imos[g+1]+=1
        imos[(g+1)%m]+=val-1
        imos[(g+1)%m+1]+=-(val-1)

for i in range(1,m+1):
    imos[i]+=imos[i-1]

for i in range(1,m+1):
    imos[i]+=imos[i-1]

ans=-1
val=0
for i in range(m):
    if val>=imos[i]:
        ans=i
        val=imos[i]

val=0
for i in range(0,n-1):
    s,g=a[i],a[i+1]
    if (g-s)%m>1:
        if g>=s:
            if g>=ans>s:
                val+=1+(g-ans)%m
            else:
                val+=(g-s)%m
        else:
            if ans>s or g>=ans:
                val+=1+(g-ans)%m
            else:
                val+=(g-s)%m
    else:
        val+=(g-s)%m


print(val)

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)



n, m = map(int, input().split())
a = list(map(int, input().split()))

bit = BIT(2 * m + 10)
cnt = 0
for i in range(n - 1):
    l, r = a[i], a[i + 1]
    if l > r:
        r += m
    cnt += r - l
    if l == r or l + 1 == r:
        continue
    if l < r:
        l += 2
        r += 1
        bit.add(l, r, 1)
        bit.add(r, r + 1, -(r - l))
        continue

imos = [0] * (2 * m + 2)
for i in range(2 * m + 2):
    imos[i] += bit.get_val(i)
    if i - 1 >= 0:
        imos[i] += imos[i - 1]

ans = [0] * (m + 1)
for i in range(1, m + 1):
    ans[i] = imos[i] + imos[i + m]
print(cnt - max(ans))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    a = LI()
    ans = sum([(a[i+1]-a[i])%m for i in range(n-1)])
    s = [0]*(2*m)
    f = [0]*(2*m)
    x = a[0]-1
    for i in range(1,n):
        y = a[i]-1
        if y < x:
            y += m
        if x+1 >= y:
            x = a[i]-1
            continue
        s[x+2] += 1
        s[y+1] -= 1
        f[y+1] -= y-x-1
        x = a[i]-1
    for i in range(2*m-1):
        s[i+1] += s[i]
        f[i+1] += f[i]+s[i+1]
    f = [f[i]+f[i+m] for i in range(m)]
    print(ans-max(f))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import *

n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x-1, a))
lr = []
cnt = 0

for i in range(n-1):
    ai, aj = a[i], a[i+1]
    
    if ai<aj:
        lr.append((ai+1, aj))
        cnt += aj-ai
    else:
        lr.append((ai-m+1, aj))
        lr.append((ai+1, m-1))
        cnt += m+aj-ai
    
lr.sort(key=lambda t: t[0])
#print(lr)
idx = 0
ans = cnt
decre = 0
pq = []

for i in range(m):
    while len(pq)>0 and pq[0][0]<i:
        r, l = heappop(pq)
        #print(l, r, decre)
        decre -= r-l+1
        
    while idx<len(lr) and i>=lr[idx][0]:
        decre += i-lr[idx][0]
        #print(decre)
        heappush(pq, (lr[idx][1], lr[idx][0]))
        idx += 1
    
    ans = min(ans, cnt-decre)
    decre += len(pq)

print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    a = list(map(lambda x: int(x)-1, input().split()))
    event = [[] for _ in [0]*m]
    for j, i in enumerate(a):
        if j < n-1:
            A = m-a[j+1]
            if A < m:
                event[A].append((True, j))
        B = m-i
        if B < m:
            event[B].append((False, j))
    leader = 1
    now = a[-1]
    for i in range(n-1):
        if a[i] > a[i+1]:
            leader += 1
            now += a[i]
    s = a[0]
    ans = 10**20
    for i in range(m):
        for e, j in event[i]:
            if e:
                leader += 1
                now += ((a[j]+i) % m)
            else:
                now -= m
                if j != n-1:
                    leader -= 1
        now += leader
        ans = min(ans, now-1-(s+i) % m)
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
d = [0] * (N - 1)
imosa = [0] * (M * 2 + 2)
imosb = [0] * (M * 2 + 2)
for i in range(N - 1):
  if a[i + 1] >= a[i]:
    d[i] = a[i + 1] - a[i]
    imosa[a[i] + 1] += 1
    imosa[a[i + 1] + 1] -= 1
    imosb[a[i] + 1] -= a[i] + 1
    imosb[a[i + 1] + 1] += a[i] + 1
  else:
    d[i] = a[i + 1] + M - a[i]
    imosa[a[i] + 1] += 1
    imosa[a[i + 1] + M + 1] -= 1
    imosb[a[i] + 1] -= a[i] + 1
    imosb[a[i + 1] + M + 1] += a[i] + 1
  #print(imosb)
#print(d)

imos = [0] * (M + 2)
for i in range(2 * M + 1):
  imosa[i + 1] += imosa[i]
  imosb[i + 1] += imosb[i]
#print(imosa)
#print(imosb)
for i in range(M + 2):
  imos[i] = imosa[i] * i + imosa[i + M] * (i + M) + imosb[i] + imosb[i + M]
#print(imos)
print(sum(d) - max(imos[1: M + 1]))

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc077/tasks/arc077_c

お気に入りを決めてる時、その数字を超えるような移動が発生した場合だけ、ボタン2が有効になる。
ALLボタン１に比べて、何回節約できるかをimos法で計算する

"""

n,m = map(int,input().split())

lis = [0] * m

state = [0] * n

a = list(map(int,input().split()))
for i in range(n):
    a[i] -= 1

start = [ [] for i in range(m) ]
end = [ [] for i in range(m)]

allsum = 0
for i in range(n-1):

    allsum += (a[i+1]-a[i]) % m
    if a[i+1] == (a[i]+1)%m:
        continue

    start[(a[i]+1) % m].append(i)
    end[a[i+1] % m].append(i)

    


imosnum = 0
plus = 0

#print (start,end)

for i in range(2*m):

    plus += imosnum

    lis[i%m] += plus

    for j in end[i%m]:
        if state[j] == 1:
            plus -= ((a[j+1]-(a[j]+1))%m)
            state[j] = 2
            imosnum -= 1

    for j in start[i%m]:
        if state[j] == 0:
            imosnum += 1
            state[j] = 1

    #print (i+1,imosnum,plus)

if (allsum - max(lis) < 0):
    print (asxacscd)
#print (lis)
print (allsum - max(lis))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
input = sys.stdin.readline
n,m = map(int,input().split())
a = list(map(int,input().split()))
ls_0 = [0 for i in range(m*2+2)]
ans_0 = 0
for i in range(1,n):
  if a[i-1] < a[i]:
    l = a[i-1]+2
    r = a[i]+1
  else:
    l = a[i-1]+2
    r = a[i]+m+1
  ls_0[l] += 1
  ls_0[r] -= (r-l+1)
  ls_0[r+1] += r-l
  ans_0 += r-l+1

ls_1 = list(accumulate(ls_0))
ls_2 = list(accumulate(ls_1))
ls_3 = [0]+[ls_2[i]+ls_2[i+m] for i in range(1,m+1)]
print(ans_0-max(ls_3))

Submission status: Accepted

Solution code:
from itertools import accumulate
n,m = map(int,input().split())
a = list(map(int,input().split()))
ls_0 = [0 for i in range(m*2+2)]
ans_0 = 0
for i in range(1,n):
  if a[i-1] < a[i]:
    l = a[i-1]+2
    r = a[i]+1
  else:
    l = a[i-1]+2
    r = a[i]+m+1
  ls_0[l] += 1
  ls_0[r] -= (r-l+1)
  ls_0[r+1] += r-l
  ans_0 += r-l+1

ls_1 = list(accumulate(ls_0))
ls_2 = list(accumulate(ls_1))
ls_3 = [0]+[ls_2[i]+ls_2[i+m] for i in range(1,m+1)]
print(ans_0-max(ls_3))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
As = list(map(int, input().split()))

ans = 0
numSts, numEns, sumEns = [0]*(2*M), [0]*(2*M), [0]*(2*M)
for i in range(N-1):
    A, B = As[i]-1, As[i+1]-1
    if A > B:
        B += M
    ans += B-A
    if B-A > 1:
        numSts[A+2] += 1
        numEns[B+1] += 1
        sumEns[B+1] += B-A-1

nums = [0]*M
num = 0
k = 0
for i in range(2*M):
    k += numSts[i] - numEns[i]
    num += k
    num -= sumEns[i]
    nums[i%M] += num

print(ans - max(nums))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))

imos = [0] * (2 * m)
diff = [0] * (2 * m)
res = 0
for i in range(n - 1):
    l = a[i] - 1
    r = a[i + 1] - 1
    if l > r:
        r += m
    imos[l + 2] += 1
    imos[r + 1] -= 1
    diff[r + 1] += r - l - 1
    res += r - l

ans = [0] * (2 * m)
tmp = 0
for i in range(2 * m):
    tmp += imos[i]
    if i - 1 >= 0:
        ans[i] += ans[i - 1] + tmp
    else:
        ans[i] += tmp
    ans[i] -= diff[i]
    
max_ = 0
for i in range(m):
    max_ = max(max_, ans[i] + ans[i + m])
print(res - max_)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n, m = MI()
    # 明るさaは0-indexedにする
    aa = LI1()
    # 頂点xをお気に入りにしたときのスコアをpx+qで表す
    # imos法を使う
    pp = [0] * (m + 1)
    qq = [0] * (m + 1)

    for a0, a1 in zip(aa, aa[1:]):
        if a0 < a1:
            pp[a0 + 1] += -1
            pp[a1 + 1] += 1
            qq[0] += a1 - a0
            qq[a0 + 1] += a0 + 1
            qq[a1 + 1] += -a0 - 1
        else:
            pp[0] += -1
            pp[a1 + 1] += 1
            pp[a0 + 1] += -1
            qq[0] += a1 + 1
            qq[a1 + 1] += m - a0 - 1
            qq[a0 + 1] += a0 + 1
    for i in range(1, m):
        pp[i] += pp[i - 1]
        qq[i] += qq[i - 1]
    ans = min(pp[i] * i + qq[i] for i in range(m))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

N,M,*A = map(int,read().split())

def f(x,y,k):
    if x > y:
        y += M
    if k <= x:
        k += M
    if k <= y:
        return (y-k) + 1
    return y-x

add_X = 0
add_DX = 0
DDX = [0] * M
for x,y in zip(A,A[1:]):
    x -= 1
    y -= 1
    a = f(x,y,M-2)
    b = f(x,y,M-1)
    add_X += b
    add_DX += b-a
    d = y - x
    if d < 0:
        d += M
    DDX[(y+1)%M] += d
    DDX[(y+2)%M] -= (d-1)
    DDX[(x+2)%M] -= 1

DX = [add_DX + y for y in itertools.accumulate(DDX)]
X = [add_X + y for y in itertools.accumulate(DX)]

answer = min(X)
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))

start = [0]*M
end = [0]*M
S = [0]*M
a = 0
score = 0
total = 0
for i in range(N-1):
    p, q = A[i]-1, A[i+1]-1
    start[q] += 1
    end[p] += 1
    S[q] += (q-p-1+M)%M
    total += (q-p+M)%M
    score += max(0, (q-p-1+M)%M - q)
    if p > q:
        a += 1

ans = total - score
ind = M-1
for _ in range(4*M):
    a -= end[ind]
    score += S[ind] - a
    a += start[ind]
    ind -= 1
    if ind < -M: ind += M
    ans = min(ans, total-score)
print(ans)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

counts = [0] * (M + 1)
for a, b in zip(A, A[1:]):
    counts[b] += (b - a) % M
A = np.array(A, dtype=int)
diffs = np.diff(A)
S = (diffs % M).sum()
# お気に入りを1にしたらこれだけ減らせる
reduce = (M - A[:-1][diffs < 0]).sum()
d = (diffs < 0).sum()
ans = S
for x in range(1, M + 1):
    ans = min(ans, S - reduce)
    reduce += d - counts[x]
    if A[0] == x:
        d += 1
    if A[-1] == x:
        d -= 1
print(ans)
# reduces = [0] * N
# s = A[0]
# A[]
# for a in
#
# A[1:].sum()

Submission status: Accepted

Solution code:
class Binary_Indexed_Tree():
    def __init__(self, n):
        self.bit = [0]*n
        self.n = n
    def add(self, ind, num):
        while(ind <= self.n):
            self.bit[ind - 1] += num
            ind += ind & -ind
    def sum(self, ind):
        ret = 0
        while(ind > 0):
            ret += self.bit[ind-1]
            ind -= ind & -ind
        return ret

class Binary_Indexed_Tree_RAQ_RSQ():
    def __init__(self,n):
        self.p = Binary_Indexed_Tree(n+1)
        self.q = Binary_Indexed_Tree(n+1)

    def add(self, s,t,x):
        t += 1
        self.p.add(s,-x*s)
        self.p.add(t, x*t)
        self.q.add(s,x)
        self.q.add(t,-x)

    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t)*t - self.p.sum(s) - self.q.sum(s)*s

n,m = map(int, input().split())
a = list(map(lambda x: int(x)-1, input().split()))
score = Binary_Indexed_Tree_RAQ_RSQ(2*m+10)


for i in range(n-1):
    cur, nxt = a[i], a[i+1]
    if cur > nxt:
        nxt += m
    if cur + 2 <= nxt:
        score.add(cur+3, nxt+1, 1)
        k = nxt-cur-1
        score.add(nxt+2, nxt+2, -k)

scores = [score.sum(0, i+1)+score.sum(0, i+m+1) for i in range(m)]

x = tmp = 0
for i in range(m):
    if scores[i] > tmp:
        x = i
        tmp = scores[i]
ans = 0

def cnt(cur, nxt):
    if cur > nxt:
        nxt += m
    return nxt-cur

for i in range(n-1):
    cur, nxt = a[i], a[i+1]
    ans += min(cnt(cur, nxt), cnt(x, nxt)+1)

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
A = list(map(lambda x:int(x)-1, input().split()))
value = [0]*(m+1)
length = [0]*(m+1)
ans = 0
for i in range(1, n):
    a, b = A[i-1], A[i]
    if a<b:
        value[a+1]+=1
        value[b+1]-=1
        length[b+1]-=(b-a)
        ans+=b-a
    else:
        value[a+1]+=1
        value[m]-=1
        value[0]+=1
        value[b+1]-=1
        length[0]+=(m-a-1)
        length[b+1]-=(m-a)+(b)
        ans+=m-a+b
for i in range(m):
    value[i+1] = value[i]+value[i+1]
for i in range(m+1):
    length[i] += value[i]
for i in range(m):
    length[i+1] += length[i]
for i in range(m):
    length[i]-=value[i]
ans -= max(length[::-1])
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
from collections import Counter

n, m = [int(item) for item in input().split()]
a = [int(item) - 1 for item in input().split()]
cnt_t = [0] * m

ans = [0] * m
cnt_r = [0] * (m + 1)
for a1, a2 in zip(a, a[1:]):
    ans[0] += min((m + a2 - a1) % m, (m + a2 - 0) % m + 1)
    cnt_t[a2] += (m + a2 - a1) % m - 1
    if (m + a2 - a1) % m <= 1:
        continue
    add = (a1 + 2) % m
    sub = a2 + 1
    if add < sub:
        cnt_r[add] += 1
        cnt_r[sub] -= 1
    else:
        cnt_r[add] += 1
        cnt_r[sub] -= 1
        cnt_r[0] += 1
        cnt_r[m] -=1
for i in range(m):
    cnt_r[i+1] += cnt_r[i]

for i in range(1, m):
    ans[i] = ans[i - 1] - cnt_r[i] + cnt_t[i - 1]
print(min(ans))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N,M = map(int,input().split())
    A = list(map(int,input().split()))
    S = [0]*(2*M+3)
    for i in range(N-1):
        now = A[i]
        nex = A[i+1]
        L = nex-now
        if L-1>0:
            S[now+2] += 1
            S[nex+1] += -L
            S[nex+2] += L-1
        elif L<0:
            L = L%M
            if L-1>0:
                S[now+2] += 1
                S[nex+1+M] += -L
                S[nex+2+M] += L-1
        #print(S)
    #print(S)
    for i in range(2*M+2):
        S[i+1] += S[i]
    #print(S)
    for i in range(2*M+2):
        S[i+1] += S[i]
    #print(S)
    B = [0]*(M+1)
    for i in range(1,M+1):
        B[i] = S[i] + S[i+M]
    X = 1
    diff = 0
    for i in range(1,M+1):
        if B[i] > diff:
            diff = B[i]
            X = i
    SS = 0
    for i in range(N-1):
        SS += (A[i+1]-A[i])%M
    #print(B)
    print(SS-diff)        
            
    
    
main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res

def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()

    return

#B
def B():
    n = I()

    return

#C
def C():
    n,m = LI()
    a = LI()
    for i in range(n):
        a[i] -= 1
    b = [0]*(m+10)
    ans = 0
    f = [0]*(m+10)
    for i in range(n-1):
        r = (a[i+1]-a[i])%m
        ans += r
        if r < 2:
            continue
        if a[i+1] >= (a[i]+2)%m:
            f[(a[i]+2)%m] += 1
            b[(a[i]+2)%m] += 1
            b[a[i+1]+1] -= 1
            f[a[i+1]+1] -= r
        else:
            b[0] += 1
            f[0] += (-a[i]-1)%m
            b[a[i+1]+1] -= 1
            f[a[i+1]+1] -= r
            b[a[i]+2] += 1
            f[a[i]+2] += 1
            b[m] -= 1
    for i in range(m-1):
        b[i+1] += b[i]
    for i in range(m-1):
        f[i+1] += f[i]+b[i]
    print(ans-max(f))
    return

#D
def D():
    n = I()

    return

#E
def E():
    n = I()

    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
P = 300005
d1 = [0] * P
d2 = [0] * P
s = 0
for i in range(N - 1):
    x = a[i]
    y = a[i + 1]
    if y < x:
        y += M
    s += y - x
    if x + 1 < y:
        d1[x + 2] += 1
        d1[y + 1] -= 1
        d2[y + 1] += y - x - 1
        d1[M + x + 2] += 1
        d1[M + y + 1] -= 1
        d2[M + y + 1] += y - x - 1

ans = float('inf')
for i in range(3 * M):
    if i > 0:
        d1[i] += d1[i - 1]
        d2[i] += d2[i - 1]
    d2[i] -= d1[i]
    ans = min(ans, s + d2[i])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


n, m = map(int, input().split())
light_list = list(map(int, input().split()))
ret = 0

diff_dict = defaultdict(int)
cnt=0
for i in range(n-1):
    if light_list[i+1] > light_list[i]:
        diff_dict[light_list[i+1]+1] += light_list[i+1] - light_list[i]
        ret += light_list[i+1] - light_list[i]
    else:
        diff_dict[light_list[i+1]+1] += m - (light_list[i] - light_list[i+1])
        ret += light_list[i+1]
        cnt += 1


ret_min = float('inf')
for i in range(1, m+1):
    if i-1 == light_list[0]:
        cnt += 1
    if i-1 == light_list[-1]:
        cnt -= 1
    if diff_dict[i]:
        ret += diff_dict[i]
    ret -= cnt
    ret_min = min(ret+cnt, ret_min)




print(ret_min)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import itertools

"""
(a_i+1,a_{i+1}] に x がある間は...使う。傾き-1
a_{i+1} -> a_{i+1} + 1 のところでがくっと下がる
そこからa_iまでは傾き0
""" 

N,M = map(int,input().split())
A = [int(x) for x in input().split()]
FROM = A[:-1]
TO = A[1:]

d_slope = [0] * (M+1) # 傾きの差分

"""
5,4,3,2,1,5,5,5,5
0,-1,-1,-1,-1,4,0,0,0
0,-1,0,0,0,0,5,-4,0,0
"""

for x,y in zip(FROM,TO):
    if y < x:
        y += M
    z = y - x
    if z == 1:
        continue
    d_slope[1+(x+1)%M] += -1
    d_slope[1+y%M] += z # 1回で行けたのがz回かかるようになる
    d_slope[1+(y+1)%M] += 1-z

slope = list(itertools.accumulate(d_slope))
S = sum(slope)
slope = [x - S//M for x in slope]
slope[0] = 0

# 1番をお気に入りにしたときのスコアを求める
cnt = 0
for x,y in zip(FROM,TO):
    if x < y:
        cnt += (y-x)
    else:
        cnt += y

answer = cnt - slope[1] + min(itertools.accumulate(slope[1:]))
print(answer)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [b-1 for b in a]
imos = [0 for _ in range(m+1)]
base = 0
for i in range(n-1):
	x, y = a[i], a[i+1]
	if y-x == 1 or x+1-m == y:
		continue
	z, w = (x+2)%m, (y+1)%m
	if w == 0:
		w = m
	if z < w:
		imos[z] += 1
		imos[w] -= w-z+1
		if w < m:
			imos[w+1] += w-z
	else:
		imos[z] += 1
		imos[m] -= m-z+1
		imos[0] += 1
		base += m-z
		imos[w] -= m+w-z+1
		if w < m:
			imos[w+1] += m+w-z
#print(imos)
#print(base)
for i in range(m):
	imos[i+1] += imos[i]
imos[0] += base
for i in range(m):
	imos[i+1] += imos[i]
res = max(imos[:m])
ans = 0
for i in range(n-1):
	if a[i+1] > a[i]:
		ans += a[i+1] - a[i]
	else:
		ans += a[i+1] + m - a[i]
#print(ans)
ans -= res
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
def inpl(): return list(map(int, input().split()))

N, M = inpl()
A = [a-1 for a in inpl()]
S = [0]*(M+1)
T = [0]*(M+1)

tmp = 0
for i in range(N-1):
    T[A[i+1]] += (A[i+1] + M - A[i])%M - 1
    if A[i] < A[i+1]:
        S[A[i]+1] += 1
        S[A[i+1]] -= 1
        tmp += A[i+1] - A[i]
    else:
        tmp += A[i+1] + 1
        S[0] += 1
        S[A[i+1]] -= 1
        S[A[i]+1] += 1

S = list(accumulate(S))
ans = tmp*1
for i in range(1, M):
    tmp2 = tmp + T[i-1] - S[i-1]
    ans = min(ans, tmp2)
    tmp = tmp2
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def solve(n, m, a):

    ans = 0
    s = [(a[0], 0)]
    for i in range(1, n):
        ans += (a[i] - a[i - 1]) % m
        s.append((a[i], i))
    s.sort()


    r = [0] * (m + 1)
    c = 0
    t = 0
    active = [0] * n
    j = 0
    while j < n:
        aj, _ = s[j]
        r[aj] += (aj * c - t - c)
        while j < n:
            ai, i = s[j]
            if ai != aj:
                break
            if 0 < i:
                if active[i - 1]:
                    active[i - 1] = 0
                    c -= 1
                    t -= a[i - 1]
            if i < n - 1:
                active[i] = 1
                c += 1
                t += a[i]
            j += 1

    if 0 < c:
        t -= m * c
        j = 0
        while j < n:
            aj, _ = s[j]
            r[aj] += (aj * c - t - c)
            while j < n:
                ai, i = s[j]
                if ai != aj:
                    break
                if 0 < i:
                    if active[i - 1]:
                        active[i - 1] = 0
                        c -= 1
                        t -= a[i - 1] - m
                j += 1
            if c == 0:
                break

    ans -= max(r)

    return ans


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    a = list(map(int, input().split()))

    print(solve(n, m, a))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
def acc(X): return list(accumulate(X))

N, M = map(int, input().split())
A = [int(a)-1 for a in input().split()]

X = [0] * M # 1,1,1,...
Y = [0] * M # 1,2,3,...

def tri(l, r, a = 1):
    if l < M:
        Y[l] += a
    if r + 1 < M:
        Y[r+1] -= a
        X[r+1] -= (r-l+1) * a

def box(l, r, a = 1):
    if l < M:
        X[l] += a
    if r + 1< M:
        X[r+1] -= a
    
def calc(a, b):
    if a <= b - 2:
        tri(a+2, b)
    elif a > b and a <= b + M - 2:
        tri(a+2, M-1)
        tri(0, b)
        box(0, b, -a+M-2)
        
    # print(a, b, X, Y, rev())

def rev():
    ret = acc(Y)
    ret = [X[i] + ret[i] for i in range(M)]
    return acc(ret)
    
ans = 0
for i in range(1, N):
    ans += (A[i] - A[i-1]) % M
    calc(A[i-1], A[i])

X = rev()
# print(X)
ans -= max(X)
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,m = li()
a = list(li_())

ans = [0]*m
# 1.前処理
# 1-1.a[1:]の中の x(0<= x < m)の個数
cnt_equal = [0]*m
for i in range(n-1):
    cnt_equal[a[i+1]] += (((a[i+1]+m-a[i])%m) - 1)

# 1-2.a[i]→a[i+1]の内側(両端除く)に x(0<= x < m)が入る回数
cnt_inner = [0]*(2*m+1)
for i in range(n-1):
    cnt_inner[a[i] + 1] += 1
    cnt_inner[a[i] + (a[i+1]+m-a[i])%m] -= 1
    
cnt_inner = list(accumulate(cnt_inner))
cnt_inner = [cnt_inner[i]+cnt_inner[i+m] for i in range(m)]


# 2.fav == 1 のときのシミュレーション
fav = 0
for i in range(n-1):
    ans[0] += min((a[i+1]+m-a[i])%m, 1+(a[i+1]+m-fav)%m)

# 3.favが[2,m]のとき、fav-1の情報をもとに更新
for fav in range(1,m):
    ans[fav] = ans[fav-1] + cnt_equal[fav-1] - cnt_inner[fav-1]
    
print(min(ans))