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:
n,m=map(int,input().split())
A=[int(i)-1 for i in input().split()]
ds=[0]*m
de=[[] for i in range(m)]
h,dec=0,0
for i in range(n-1):
  if A[i+1]-A[i]>0:
    h+=A[i+1]-A[i]
  else:
    h+=A[i+1]+1
    dec+=1
  de[A[i+1]].append((i,(A[i+1]-A[i])%m))
for i in range(m):
  for a in de[i]:
    ds[(i-a[1]+1)%m]+=1
ans=float("inf")
for i in range(m):
  for a in de[i]:
    h+=a[1]-1
    dec-=1
  h-=dec
  ans=min(h,ans)
  if i<=m-2:
    dec+=ds[i+1]
  
print(ans)

Submission status: Accepted

Solution code:
import itertools
def inpl(): return [int(i) for i in input().split()]

n, m = inpl()
a = [int(i)-1 for i in input().split()]
tans = [0]*2*m
Mi = []
Si = 0
for a0, a1 in zip(a, a[1:]):
    if a1 < a0:
        a1 += m
    tans[a0+2] += 1
    tans[a1+1] -= 1
    Mi.append((a1+1, 1+a0-a1))
    Si += a1 - a0
tans = list(itertools.accumulate(tans))
for x, v in Mi:
    tans[x] += v
tans = list(itertools.accumulate(tans))
ans = [0]*m
for i, v in enumerate(tans):
    ans[i%m] += v
print(Si - max(ans))

Submission status: Accepted

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

D0 = [0]*(2*m+10)
D1 = [0]*(2*m+10)
ans = 0

pa = A[0]-1
for a in A[1:]:
    a -= 1
    if a<pa:
        a += m
    ans += a-pa
    D1[pa+1] += 1
    D1[a] -= a-pa
    D1[a+1] += a-pa-1
    pa = a%m

for i, d1 in enumerate(D1):
    D0[i] = d1 + D0[i-1]

L = [0]*(2*m+10)

for i, d0 in enumerate(D0):
    L[i] = d0 + L[i-1]

for i, l in enumerate(L[m:]):
    L[i%m] += l

print(ans-max(L[:m]))

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math
import re

sys.setrecursionlimit(1000000)

n, m = map(int, raw_input().split())
a = map(int, raw_input().split())

a_pre = a[0]
d1 = [0] * (m + 2)
d0 = [0] * (m + 2)
ans = 0
for i in range(1, n):
    a_cur = a[i]
    ans += (a_cur - a_pre) % m
    if a_pre < a_cur:
        d1[a_pre + 1] += 1
        d1[a_cur + 1] -= 1
        d0[a_pre + 1] -= a_pre + 1
        d0[a_cur + 1] += a_pre + 1
    else:
        d1[a_pre + 1] += 1
        d0[a_pre + 1] -= a_pre + 1
        d1[1] += 1
        d1[a_cur + 1] -= 1
        d0[1] += m - a_pre - 1
        d0[a_cur + 1] -= m - a_pre - 1
    a_pre = a[i]

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

dec = [d1[i] * i + d0[i] for i in range(m + 1)]
print ans - max(dec)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M = inpl()
aa = inpl()
for i in range(N):
	aa[i] -= 1

yama_height = [0]*(2*M)
yama_num = [0]*(2*M)
SUM = 0
for i in range(1,N):
	na = aa[i]
	ba = aa[i-1]
	if na < ba:
		na += M
	SUM += (na-ba)
	yama_height[na] += na - (ba + 1)
	yama_num[na] -= 1
	yama_num[ba+1] += 1

tmp = 0
for i in range(2*M):
	tmp += yama_num[i]
	yama_num[i] = tmp

ans_list = [0]*(M)
tmp = 0
for i in reversed(range(2*M)):
	tmp += yama_height[i]
	tmp -= yama_num[i]
	ans_list[i%M] += tmp

print(SUM-max(ans_list))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
src = list(map(lambda x:int(x)-1,input().split()))

imos = [0] * (2*M+1)
ends = [0] * (2*M+1)
max_press = 0
for a,b in zip(src,src[1:]):
    if a > b:
        b += M
    if b-a > 1:
        imos[a+2] += 1
        imos[b+1] -= 1
        ends[b+1] += b-a-1
    max_press += b-a

for i in range(2*M):
    imos[i+1] += imos[i]

press = [max_press] * M
d = 0
for i,(dec,inc) in enumerate(zip(imos, ends)):
    d += inc - dec
    press[i%M] += d
print(min(press))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = list(map(int, input().split()))
bitween = [0 for i in range(2 * m + 10)]
edge = [[] for i in range(m + 1)]

ans = 0
for i in range(n - 1):
	l, r = a[i], a[i + 1]
	if l >= r:
		r += m
	bitween[l + 2] += 1
	bitween[r + 1] -= 1

	edge[a[i + 1]].append(i)

for i in range(2 * m + 1):
	bitween[i + 1] += bitween[i]

ans = 0
for i in range(n - 1): # x = 1
	ans += min((a[i + 1] - a[i] + m) % m, (a[i + 1] - 1 + m) % m + 1)
prv = ans
for i in range(2, m + 1): # x >= 2
	crt = prv - bitween[i] - bitween[i + m]
	for j in edge[i - 1]:
		crt -= min((a[j + 1] - a[j] + m) % m, (a[j + 1] - (i - 1) + m) % m + 1)
		crt += min((a[j + 1] - a[j] + m) % m, (a[j + 1] - i + m) % m + 1 )
	ans = min(ans, crt)
	prv = crt
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
a=list(map(int,input().split()))
s=[0]*(2*m+2)
tot=0
for l,r in zip(a,a[1:]):
	tot+=(r-l)%m
	if l>r:
		r+=m
	dif=r-l
	if dif>1:
		s[l+2]+=1
		s[r+1]-=dif
		s[r+2]+=dif-1
s=list(itertools.accumulate(list(itertools.accumulate(s))))
print(tot-max(s[i]+s[m+i] for i in a))

Submission status: Accepted

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


A = [int(s) for s in input().split()]

A = [(a-A[0])%m for a in A]

end = A[-1]

dist = [0]*m
cycles = 0
x = 0

for a,b in zip(A[:-1],A[1:]):
  cycles += b < a
  dist[b] += (b-a)%m
  x += min((b-a)%m, 1 + b)

dist[0] += 1

res = x

for k in range(m):

  x += dist[k]
  x -= cycles + (k <= end)

  res = min(res, x)

print(res)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def M(n): return ModInt(n)
def MI(): return M(I())

class ModInt():
    def __init__(self, n):
        self.n = n

    def __add__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n+x) % mod)

    def __sub__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n-x) % mod)

    def __mul__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n*x) % mod)

    def __truediv__(self, x):
        x = ModInt.xn(x)
        return ModInt(self.n * pow(x, mod-2, mod) % mod)

    @classmethod
    def xn(cls, x):
        if isinstance(x, ModInt):
            return x.n
        return x

    def __str__(self):
        return str(self.n)

def main():
    n,m = LI()
    a = LI_()
    b = [0] * (m*2)
    c = [[] for _ in range(m*2)]
    r = 0
    for i in range(1,n):
        d = a[i-1]
        e = a[i]
        if e < d:
            e += m
        b[d+2] += 1
        c[e].append(e-d-1)
        r += e-d

    f = [0] * (m*2)
    t = 0
    tt = 0
    for i in range(1,m*2):
        t += b[i]
        tt += t
        f[i] += tt
        for g in c[i]:
            t -= 1
            tt -= g
    for i in range(m):
        f[i] += f[i+m]

    return r - max(f)

print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate

n, m = map(int, input().split())
aa = list(map(int, input().split()))
counter = defaultdict(list)

cum = [0] * (m + 2)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    cum[a + 1] += 1
    cum[b] += -1
    if a > b:
        cum[1] += 1
        ans_1 += b
    else:
        ans_1 += b - a

cum = list(accumulate(cum))

ans_prev = ans_1
ans_min = ans_1
for x in range(1, m):
    ans_x = ans_prev
    if x in counter:
        ans_x += sum((x - a) % m - 1 for a in counter[x])
    ans_x -= cum[x]
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate

n, m = map(int, input().split())
aa = list(map(int, input().split()))
counter = defaultdict(list)

cum = [0] * (m + 2)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    cum[a + 1] += 1
    cum[b] += -1
    if a > b:
        cum[1] += 1
        ans_1 += b
    else:
        ans_1 += b - a

cum = list(accumulate(cum))

ans_prev = ans_1
ans_min = ans_1
for x in range(2, m + 1):
    ans_x = ans_prev
    px = x - 1
    if px in counter:
        ans_x += sum((px - a) % m - 1 for a in counter[px])
    ans_x -= cum[px]
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)

Submission status: Accepted

Solution code:
from collections import defaultdict


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, m = map(int, input().split())
aa = list(map(int, input().split()))
counter = defaultdict(list)

bit = Bit(m + 1)
ans_1 = 0
for a, b in zip(aa, aa[1:]):
    counter[b].append(a)
    bit.add(a + 1, 1)
    bit.add(b, -1)
    if a > b:
        bit.add(1, 1)
        ans_1 += b
    else:
        ans_1 += b - a

ans_prev = ans_1
ans_min = ans_1
for x in range(2, m + 1):
    ans_x = ans_prev
    px = x - 1
    if px in counter:
        ans_x += sum((px - a) % m - 1 for a in counter[px])
    ans_x -= bit.sum(px)
    ans_min = min(ans_min, ans_x)
    ans_prev = ans_x
print(ans_min)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
a = map(int, raw_input().split())
s = [0] * (2 * m + 1)
cnt = [0] * (m + 1)
for i in xrange(n - 1):
    cnt[a[i + 1]] += (a[i + 1] + m - a[i]) % m - 1
for i in xrange(n - 1):
    s[a[i] + 1] += 1
    if a[i + 1] < a[i]:
        s[a[i + 1] + m] -= 1
    else:
        s[a[i + 1]] -= 1

for i in xrange(2 * m):
    s[i + 1] += s[i]
for i in xrange(1, m + 1):
    s[i] = s[i] + s[i + m]

tmp = 0
for i in xrange(n - 1):
    if a[i + 1] < a[i]:
        tmp += (a[i + 1] - 1) + 1
    else:
        tmp += (a[i + 1] - a[i])
ans = tmp
for i in xrange(2, m + 1):
    tmp = tmp + cnt[i - 1] - s[i - 1]
    ans = min(ans, tmp)
print ans

Submission status: Accepted

Solution code:
_,m,*A=map(int,open(0).read().split());S=l=3*m;D=[0]*l
for a,b in zip(A,A[1:]):b+=m*(b<a);k=b-a;S+=k;D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
for i in range(l*2):D[i%l]+=D[~-i%l]
print(S-l-max(D[a]+D[a+m]for a in A))

Submission status: Accepted

Solution code:
_,m,*A=map(int,open(0).read().split());S=l=3*m;D=[0]*l
for a,b in zip(A,A[1:]):b+=m*(b<a);k=b-a;S+=k;D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec("for i in range(l):D[i]+=D[i-1]\n"*2);print(S-l-max(D[a]+D[a+m]for a in A))

Submission status: Accepted

Solution code:
_,m,*A=map(int,open(0).read().split());S=l=3*m;D=[0]*l
for a,b in zip(A,A[1:]):
 b+=m*(b<a);k=b-a;S+=k
 if k>1:D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec("for i in range(l):D[i]+=D[i-1]\n"*2);print(S-l-max(D[a]+D[a+m]for a in A))

Submission status: Accepted

Solution code:
n,m,*A=map(int,open(0).read().split());l=3*m;D=[0]*l;S=0
for a,b in zip(A,A[1:]):
 b+=m*(b<a);k=b-a;S+=k
 if k>1:D[a+2]+=1;D[b+1]-=k;D[b+2]+=k-1
exec("for i in range(1,l):D[i]+=D[i-1]\n"*2);print(S-max(D[a]+D[a+m]for a in A))

Submission status: Accepted

Solution code:
n,m,*A=map(int,open(0).read().split())
D=[0]*(2*m+2)
cur = 0
S = 0
for a,b in zip(A,A[1:]):
    S += (b-a)%m
    b += m*(b<a)
    k = b-a
    if k>1:
        D[a+2] += 1
        D[b+1] -= k
        D[b+2] += k-1
for i in range(1,2*m+2):
    D[i]+=D[i-1]
for i in range(1,2*m+2):
    D[i]+=D[i-1]
print(S-max(D[a]+D[a+m]for a in A))

Submission status: Accepted

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

def solve(n, m, As):
    weighted_sum = [0] * m
    row_sum = [0] * m
    col_sum = [0] * m
    delta_sum = [0] * m
    delta_sum0 = 0
    delta_weighted = 0
    sol = 0
    As = [a - 1 for a in As]
    for i in range(n - 1):
        a = As[i]
        b = As[i + 1]
        sol += (b - a) % m
        if a == b or (a + 1)%m == b: continue
        row_sum[a] += 1
        col_sum[b] += 1
        weighted_sum[b] += (b - a - 1) % m
        if (a > b and a != m - 1):
            delta_sum0 += 1
            delta_weighted += m - a - 1
    delta_sum[0] = delta_sum0
    for i in range(1, m):
        delta_sum0 = delta_sum0 + row_sum[i - 2] - col_sum[i - 1]
        delta_sum[i] = delta_sum0
    record = delta_weighted
    for x in range(1, m):
        delta_weighted += delta_sum[x] - weighted_sum[x - 1]
        record = max(record, delta_weighted)
    return sol - record
    
print(solve(n, m, As))

Submission status: Accepted

Solution code:
# E
n, m = map(int, input().split())
a_list = list(map(int, input().split()))


# bonus map
bonus_str_cnt = [0]*(m+1)
bonus_end_vol = [0]*(m+1)
bonus_end_cnt = [0]*(m+1)

# 1
one_res = 0
bonus_cnt = 0
for i in range(n-1):
    difm = (a_list[i+1] - a_list[i]) % m
    if difm > 1:
        if a_list[i] + 2 > m:
            bonus_str_cnt[(a_list[i] + 2) - m] += 1
        else:
            bonus_str_cnt[a_list[i] + 2] += 1
        bonus_end_cnt[a_list[i+1]] += 1
        bonus_end_vol[a_list[i+1]] += difm - 1
    if difm <= a_list[i+1]:
        one_res += difm
    else:
        one_res += a_list[i+1]
        bonus_cnt += 1

res_list = [one_res]
res = one_res
for i in range(2, m+1):
    res += bonus_end_vol[i-1]
    bonus_cnt += bonus_str_cnt[i] - bonus_end_cnt[i-1]
    res -= bonus_cnt
    res_list.append(res)

print(min(res_list))

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
A = map(int, raw_input().split())
S = 0
for i in xrange(n-1):
    S += (m + A[i+1] - A[i]) % m

T = 2*m
D = [0]*(T+10)
data = [0]*(T+1)
def get(i):
    s = 0
    while i:
        s += data[i]
        i -= i & -i
    return s
def add(i, x):
    while i <= T:
        data[i] += x
        i += i & -i

for i in xrange(n-1):
    x = A[i]; y = A[i+1]
    if y < x:
        y += m
    k = y-x
    if k > 1:
        D[x+2] += 1
        D[y+1] -= k
        D[y+2] += k-1
for i in xrange(1, 2*m+5):
    D[i] += D[i-1]
    add(i, D[i])
res = min(S - (get(a) + get(a+m)) for a in A)
print res

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

n, m = [int(c) for c in input().split()]
xs = [int(c) for c in input().split()]


def ring_cost(fr, to):
    return to - fr if to >= fr else (m - fr) + to

from_counter = Counter(xs[:-1])
to_counter = Counter(xs[1:])

fav = 1
cost = 0
use_fav = 0
nofav_cost = defaultdict(int)

for i in range(n - 1):
    normal_cost = ring_cost(xs[i], xs[i+1])
    fav_cost = ring_cost(fav, xs[i+1]) + 1
    cost += min(normal_cost, fav_cost)
    nofav_cost[xs[i+1]] += normal_cost
    if fav_cost <= normal_cost:
        use_fav += 1

ans = cost
for fav in range(2, m+1):
    stop_using_fav = to_counter[fav - 1]
    use_fav -= stop_using_fav
    cost += nofav_cost[fav - 1] - stop_using_fav

    cost -= use_fav

    use_fav += from_counter[fav - 1]
    ans = min(ans, cost)
    # print(fav, cost)

print(ans)

Submission status: Runtime Error

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()))

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

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

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

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

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


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 (allsum - max(lis))

Submission status: Runtime Error

Solution code:
n, m = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

def calc(l, m1, m2, r):
    val = [0] * 4
    for a1, a2 in zip(a, a[1:]):
        diff = (a2 - a1 + m) % m
        val[0] += min(diff, (a2 - l + m) % m + 1)
        val[1] += min(diff, (a2 - m1 + m) % m + 1)
        val[2] += min(diff, (a2 - m2 + m) % m + 1)
        val[3] += min(diff, (a2 - r + m) % m + 1)
    return val.index(min(val)), min(val)

l = 1; r = m
while r - l > 2:
    m1 = (l * 2 + r) // 3
    m2 = (l + r * 2) // 3
    ret, _ = calc(l, m1, m2, r)
    if ret == 0:
        r = m1
    elif ret == 1:
        r = m2
    elif ret == 2:
        l = m1
    else:
        l = m2
_, ans = calc(l, m1, m2, r)
print(ans)

Submission status: Runtime Error

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

def main():
    N, M = map(int, input().split())
    a = list(map(int, input().split()))

    tmp = sorted(list(set(a[1:])))
    max_ = tmp[1] - tmp[0]
    ind = tmp[1]
    pre = tmp[1]
    for i in range(2, len(tmp)):
        if tmp[i] - pre > max_:
            max_ = tmp[i] - pre
            ind = tmp[i]
        pre = tmp[i]
    if tmp[0] + M - pre > max_:
        max_ = tmp[0] + M - pre
        ind = tmp[0]
    # print(max_, ind)
    use_like = [0] * N
    for i in range(1, N):
        if ind <= a[i]:
            use_like[i] = a[i] - ind + 1
        else:
            use_like[i] = a[i] + M - ind + 1

    ans = 0
    pre = a[0]
    for i in range(1, N):
        if pre < a[i]:
            ans += min(a[i] - pre, use_like[i])
        else:
            ans += min(a[i] + M - pre, use_like[i])
        pre = a[i]
    # print(use_like)
    print(ans)
            


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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]
	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(n):
	imos[i+1] += imos[i]
imos[0] += base
for i in range(n):
	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: Runtime Error

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]
	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
		imos[w+1] += m+w-z
#print(imos)
#print(base)
for i in range(n):
	imos[i+1] += imos[i]
imos[0] += base
for i in range(n):
	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: Runtime Error

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+1, M-1)
        tri(0, b)
        box(0, b, b-a-1)

ans = 0
for i in range(1, N):
    ans += (A[i] - A[i-1]) % M
    calc(A[i-1], A[i])

Y = acc(Y)
X = [X[i] + Y[i] for i in range(N)]
X = acc(X)

ans -= max(X)
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
input_array = map(int, raw_input().split())
base_result = 0
index_dict = [0] * M
now_val = input_array[0]
for index in xrange(len(input_array)- 1):
	base_result += min((input_array[index + 1] - input_array[index]) % M,
		(input_array[index + 1]) % M + 1)
	val = input_array[index + 1]
	index_dict[val] += ((val - input_array[index]) % M - 1)
	next_val = (now_val + (val - now_val) % M)
	if now_val + 1 >= next_val:
		continue
	else:
		for val_2 in xrange(now_val + 1, next_val):
			index_dict[val_2 % M] -= 1
	now_val = next_val

best_result = base_result

for base_val in xrange(M):
	base_result += index_dict[base_val % M]
	best_result = min(base_result,best_result) 
	
print best_result

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
input_array = map(int, raw_input().split())
def count(base_val, input_array, M):
	return sum([min((input_array[i + 1] - input_array[i]) % M,
		 (input_array[i + 1] - base_val) % M + 1
		)
	 for i in xrange(len(input_array) - 1)])

base_result = count(1, input_array, M)
best_result = base_result
index_dict = [0] * M
now_val = input_array[0]
for index in xrange(len(input_array)- 1):
	val = input_array[index + 1]
	index_dict[val] += ((val - input_array[index]) % M - 1)
	next_val = (now_val + (val - now_val) % M)
	if now_val + 1 >= next_val:
		continue
	else:
		for val_2 in xrange(now_val + 1, next_val):
			index_dict[val_2 % M] -= 1
	now_val = next_val

for base_val in xrange(1, M + 1):
	base_result += index_dict[base_val % M]
	best_result = min(base_result,best_result) 
	
print best_result

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
input_array = map(int, raw_input().split())
def count(base_val, input_array, M):
	return sum([min((input_array[i + 1] - input_array[i]) % M,
		 (input_array[i + 1] - base_val) % M + 1
		)
	 for i in xrange(len(input_array) - 1)])

base_result = count(1, input_array, M)
best_result = base_result
index_dict = [0] * M
now_val = input_array[0]
for index in xrange(len(input_array)- 1):
	val = input_array[index + 1]
	index_dict[val] += ((val - input_array[index]) % M - 1)
	next_val = (now_val + (val - now_val) % M)
	if now_val + 1 >= next_val:
		continue
	else:
		for val_2 in xrange(now_val + 1, next_val):
			index_dict[val_2 % M] -= 1
	now_val = next_val

for base_val in xrange(1, M + 1):
	base_result += index_dict[base_val % M]
	best_result = min(base_result,best_result)

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
input_array = map(int, raw_input().split())
def count(base_val, input_array, M):
	return sum([min((input_array[i + 1] - input_array[i]) % M,
		 (input_array[i + 1] - base_val) % M + 1
		)
	 for i in range(len(input_array) - 1)])

from collections import defaultdict
base_result = count(1, input_array, M)
best_result = base_result
index_dict = [0] * M
now_val = input_array[0]
for index in xrange(len(input_array)- 1):
	val = input_array[index + 1]
	index_dict[val] += ((val - input_array[index]) % M - 1)
	next_val = (now_val + (val - now_val) % M)
	for val_2 in xrange(now_val + 1, next_val):
		index_dict[val_2 % M] -= 1
	now_val = next_val

for base_val in xrange(1, M + 1):
	base_result += index_dict[base_val % M]
	best_result = min(base_result,best_result) 
	


print best_result

Submission status: Runtime Error

Solution code:
input_line_1 = raw_input()
input_line_2 = raw_input()
input_array = [int(i) for i in input_line_2.split(" ")]
M = int(input_line_1.split(" ")[1])
def count(base_val, input_array, M):
	return sum([min((input_array[i + 1] - input_array[i]) % M,
		 (input_array[i + 1] - base_val) % M + 1
		)
	 for i in range(len(input_array) - 1)])

from collections import defaultdict
base_result = count(1, input_array, M)
best_result = base_result
index_dict = defaultdict(int)
now_val = input_array[0]
for index, val in enumerate(input_array[1:]):
	index_dict[val] += ((val - input_array[index]) % M - 1)
	next_val = (now_val + (val - now_val) % M)
	for val_2 in range(now_val + 1, next_val):
		index_dict[val_2 % M] -= 1
	now_val = next_val

for base_val in range(M + 1)[1:-1]:
	base_result += (index_dict2[base_val] + index_dict[base_val % M])
	best_result = min(base_result,best_result) 
	


print best_result

Submission status: Runtime Error

Solution code:
n=int(input())
m=int(input())

a=input().split()

for i in range(len(a)):
    a[i]=int(a[i])

b=[0 for i in range(m+1)]

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

max_value=0
max_num=0
for i in range(m):
    if(max_value<=b[i]):
        max_value=b[i]
        max_num=i

def move(x,y):
    result=0
    if(x<y):
        result=y-x
    else:
        result=(m-x)+y

    return result

sum_value=0
for i in range(n-1):
    sum_value+=min(move(max_num,a[i+1]),move(a[i],a[i+1]))
print(sum_value)