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: Wrong Answer

Solution code:
input_line_1 = raw_input()
input_line_2 = raw_input()
#N = int(input_line_1)
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)])

#base_result = [(input_array[i + 1] - input_array[i]) % M for i in range(len(input_array) - 1)]
def count_2(base_val, input_array, M):
	return sum([min(base_result[i],(input_array[i + 1] - base_val) % M + 1)
	for i in range(len(input_array)-1)])

def count_3(base_val, input_array, M, base_result_i):
	diff_result = 0
	for index in range(len(input_array)-1):
		if ((input_array[index] < base_val) & (base_val < input_array[index + 1])):
			diff_result -= 1
			#print "p1", input_array[index], base_val,  input_array[index + 1]
		elif ((input_array[index] < base_val) & 
			  (base_val < (input_array[index + 1] + M)) & 
			  (input_array[index + 1] < input_array[index] < 0)
			  ):
			diff_result -= 1
			#print "p2", input_array[index], base_val,  input_array[index + 1]
		elif input_array[index + 1] == base_val:
			diff_result += (input_array[index + 1] - input_array[index] - 1) % M
			#print "p3", input_array[index], base_val,  input_array[index + 1]
	return base_result_i + diff_result

base_result = count(1, input_array, M)
best_result = base_result
for base_val in range(M + 1)[1:-1]:
	#print base_val,base_result,best_result 
	base_result = count_3(base_val, input_array, M, base_result)
	best_result = min(base_result,best_result) 


print best_result

Submission status: Wrong Answer

Solution code:
c=input().split()
a=input().split()

for i in range(2):
    c[i]=int(c[i])
n=c[0]
m=c[1]


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)

Submission status: Wrong Answer

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

# base
# base = 0

# 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:
        bonus_str_cnt[(a_list[i] + 2) % m] += 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(max(n-1, min(res_list)))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
ans=n*m
for i in range(m):#お気に入りの明るさはm(m+1)
  x=i+1
  time=0
  for i in range(n-1):
    if a[i+1]>a[i]:
      Nm=a[i+1]-a[i]
    else:
      Nm=n+a[i+1]-a[i]
    if a[i+1]>=x:
      Sp=a[i+1]-x+1
    else:
      Sp=n+a[i+1]-x+1
    time+=min(Nm,Sp)
  ans=min(time,ans)
print(ans)

Submission status: Wrong Answer

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

# base
# base = 0

# 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
bonus = 0
for i in range(n-1):
    # base += (a_list[i+1] - a_list[i]) % m
    difm = (a_list[i+1] - a_list[i]) % m
    if difm > 1:
        bonus_str_cnt[(a_list[i] + 2) % m] += 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
        bonus += difm - a_list[i+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: Wrong Answer

Solution code:
import numpy as np

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

c=[0]*(n+2)


a.append(False)
def cost(fv):
    for k in range(1,n):
        if a[k]>=a[k-1]:
            c[k]=min(a[k]-a[k-1],1+a[k]-fv)
        else:
            if a[k]>=fv:
                c[k]=min(1+a[k]-fv,
                    a[k]+m-a[k-1])
            else:
                c[k]=a[k]+m-a[k-1]


    #print(c)
    return np.sum(c)

l=0
r=m-1
while True:
    cr=cost(r)
    center=int((l+r)/2)
    ccenter=cost(center)
    if ccenter<cr:
        r=center
    else:
        l=center

    if np.abs(r-l)<=1:
        break


print(cost(center))

Submission status: Wrong Answer

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] - A[i-1]) % 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])
for i in xrange(1, 2*m+5):
    D[i] += D[i-1]
res = min(S - (get(a) + get(a+m)) for a in A)
print res

Submission status: Time Limit Exceeded

Solution code:
import operator
N, M = map(int, raw_input().split())
input_array = map(int, raw_input().split())
base_result = 0
 
index_dict = [0] * (2 * M)
now_val = input_array[0]
used_num_list = []
for index in xrange(len(input_array)- 1):
	val = input_array[index + 1]
	diff = val - now_val
	base_result += min(diff % M, (val - 1) % M + 1)
	index_dict[val % M] += (diff % M - 1)
	if (diff % M) > 1:
		#print diff % M
		#print (diff % M) * [M]
		#print range(now_val+1,now_val+(diff % M))
		index_dict[now_val+1:now_val+(diff % M)] = map(
			operator.add, index_dict[now_val+1:now_val+(diff % M)],
			[-1] * (diff % M - 1))
	now_val = val
 
 
best_result = base_result
 
for base_val in xrange(1,M):
	#print base_val,index_dict[base_val % M], used_num_list.count(base_val), base_result
	base_result += index_dict[base_val % M]
	base_result += index_dict[base_val % M + M]
	best_result = min(base_result,best_result) 
	
print best_result

Submission status: Time Limit Exceeded

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):
        b = list(map(lambda x: (x+i) % m, a))
        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: Time Limit Exceeded

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

score = [0]*(2*m)
for i in range(n-1):
    cur, nxt = a[i], a[i+1]
    if cur > nxt:
        nxt += m
    for j in range(nxt-cur):
        score[cur+j+1] -= j

for i in range(m):
    score[i] += score[i+m]

# argmin
x = tmp = 0
for i in range(m):
    if score[i] < tmp:
        x = i
        tmp = score[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: Time Limit Exceeded

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))
slope = [x - sum(slope)//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

cnt

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

Submission status: Time Limit Exceeded

Solution code:
n=10**5
a=[[0 for i in range(n)] for _ in range(n)]

Submission status: Time Limit Exceeded

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

def turn(a0, a1, x, m):
    if a1 > a0:
        d1 = a1 - a0
    else:
        d1 = a1 - a0 + m
    if x > a0:
        d2 = x - a0
    else:
        d2 = x - a0 + m
    if d1 >= d2:
        return 1+d1-d2
    else:
        return d1 

print(min([sum([turn(a[i], a[i+1], x, m) for i in range(n-1)]) for x in range(1,m+1)]))

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(int, input().split()))
ls = list(map(int, input().split()))
counter = [0 for i in range(m+1)]
t = 0

for i in range(n-1):
    a = ls[i]
    b = ls[i+1]
    if (b < a):
        b += m
    c = b - a - 1
    t += (b-a)
    for j in range(b-c+1, b+1):
        k = int(j % m)
        counter[k] += (j - b +c)

print(t - max(counter))

Submission status: Time Limit Exceeded

Solution code:
n, m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [0]*(m+1)


for i in range(0,n):
    if i == n-1:
        break
    else:
        now = a[i]
        j=0
        while now != a[i+1]:
            if now<m:
                now=now+1
                b[now]+=j
            else:
                now=1
                b[now]+=j
            j+=1
s=0
for i in range(0,n):
    if i == n-1:
        break
    d=a[i+1]-a[i]
    if d>=0:
        s+=d
    else:
        s+=m+d

print(s-max(b))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, raw_input().split())
input_array = np.array(map(int, raw_input().split()))
base_result = 0

index_dict = np.zeros((2 * M))
used_num_list = []

diff_array = (input_array[1:] - input_array[0:-1]) % M
diff_2 = (diff_array - input_array[1:])
base_result = sum(diff_array[diff_2 <= 0]) + sum(input_array[1:][diff_2 > 0])

for base_val in xrange(1,M):
	indexes = np.array(range(len(input_array)-1))[input_array[1:] == base_val]
	index_dict[base_val] += sum(diff_array[indexes]-1)

for index in np.array(range(len(diff_array)))[diff_array > 1]:
	index_dict[input_array[index]+1:input_array[index]+diff_array[index]] -= 1 

#np.array([range(input_array[index]+1,input_array[index]+diff_array[index])
#for index in np.array(range(len(diff_array)))[diff_array > 1]])
index_dict[0:M] += index_dict[M:]

best_result = base_result

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

print int(best_result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, raw_input().split())
input_array = np.array(map(int, raw_input().split()))
base_result = 0

index_dict = np.zeros((2 * M))
used_num_list = []

diff_array = (input_array[1:] - input_array[0:-1]) % M
diff_2 = (diff_array - input_array[1:])
base_result = sum(diff_array[diff_2 <= 0]) + sum(input_array[1:][diff_2 > 0])

for index in xrange(len(diff_array)):
	index_dict[input_array[index+1]] += (diff_array[index] - 1)
	if (diff_array[index]) > 1:
		index_dict[input_array[index]+1:input_array[index]+diff_array[index]] -= 1 

index_dict[0:M] += index_dict[M:]

best_result = base_result

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

print int(best_result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, raw_input().split())
input_array = np.array(map(int, raw_input().split()))
base_result = 0

index_dict = np.zeros(2 * M)
used_num_list = []

diff_array = (input_array[1:] - input_array[0:-1]) % M
diff_2 = (diff_array - input_array[1:])
base_result = sum(diff_array[diff_2 <= 0]) + sum(input_array[1:][diff_2 > 0])

for index in xrange(len(diff_array)):
	index_dict[input_array[index+1]] += (diff_array[index] - 1)
	if (diff_array[index]) > 1:
		index_dict[input_array[index]+1:input_array[index]+diff_array[index]] -= 1 


best_result = base_result

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

print int(best_result)

Submission status: Time Limit Exceeded

Solution code:
import operator
import numpy as np
N, M = map(int, raw_input().split())
input_array = map(int, raw_input().split())
base_result = 0

index_dict = np.zeros(2 * M)
now_val = input_array[0]
used_num_list = []
for index in xrange(len(input_array)- 1):
	val = input_array[index + 1]
	diff = val - now_val
	base_result += min(diff % M, (val - 1) % M + 1)
	index_dict[val % M] += (diff % M - 1)
	if (diff % M) > 1:
		index_dict[now_val+1:now_val+(diff % M)] -= 1 
	now_val = val


best_result = base_result

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

Submission status: Time Limit Exceeded

Solution code:
import operator
N, M = map(int, raw_input().split())
input_array = map(int, raw_input().split())
base_result = 0

index_dict = [0] * (2 * M)
now_val = input_array[0]
used_num_list = []
for index in xrange(len(input_array)- 1):
	val = input_array[index + 1]
	diff = val - now_val
	base_result += min(diff % M, (val - 1) % M + 1)
	index_dict[val % M] += (diff % M - 1)
	if (diff % M) > 1:
		#print diff % M
		#print (diff % M) * [M]
		#print range(now_val+1,now_val+(diff % M))
		index_dict[now_val+1:now_val+(diff % M)] = map(
			operator.add, index_dict[now_val+1:now_val+(diff % M)],
			[-1] * (diff % M - 1))
	now_val = val


best_result = base_result

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

Submission status: Time Limit Exceeded

Solution code:
import operator
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]
used_num_list = []
for index in xrange(len(input_array)- 1):
	val = input_array[index + 1]
	diff = val - now_val
	base_result += min(diff % M, (val - 1) % M + 1)
	index_dict[val % M] += (diff % M - 1)
	if (diff % M) > 1:
		#print diff % M
		#print (diff % M) * [M]
		#print range(now_val+1,now_val+(diff % M))
		used_num_list += map(operator.mod,range(now_val+1,now_val+(diff % M)), 
			((diff % M - 1) * [M]))
	now_val = val


best_result = base_result

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

Submission status: Time Limit Exceeded

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_dict[base_val % M]
	best_result = min(base_result,best_result) 
	


print best_result

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
input_line_1 = raw_input()
input_line_2 = raw_input()
#N = int(input_line_1)
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)])

base_result = count(1, input_array, M)
best_result = base_result
index_dict = defaultdict(int)
index_dict2 = defaultdict(int)
input_array_2 = [input_array[0]]
now_val = input_array[0]
for index, val in enumerate(input_array[1:]):
	index_dict[val] += ((val - input_array[index]) % M - 1)
	#input_array_2.append(input_array_2[-1] + (val - input_array_2[-1]) % M)
	next_val = (now_val + (val - now_val) % M)
	for val_2 in range(now_val + 1, next_val):
		#print val_2
		index_dict2[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 base_val, base_result,best_result
	


print best_result

Submission status: Time Limit Exceeded

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

a = [int(x) for x in input().split()]

def counter(start,goal,m):
	tmp = goal - start
	if tmp < 0:
		tmp += m
		return tmp
	else:
		return tmp

l = []

for x in range(1,m+1):
	count = 0
	for i in range(n-1):
		if (a[i]<x and x<a[i+1]) or (a[i+1]<a[i] and a[i]<x) or (x<a[i+1] and a[i+1]<a[i]) or (x==a[i+1]):
			count += 1 + counter(x, a[i+1], m)
		else:
			count += counter(a[i], a[i+1], m)
	l.append(count)

print(min(l))

Submission status: Time Limit Exceeded

Solution code:
input_line_1 = raw_input()
input_line_2 = raw_input()
#N = int(input_line_1)
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)])

base_result = [(input_array[i + 1] - input_array[i]) % M for i in range(len(input_array) - 1)]
def count_2(base_val, input_array, M):
	return sum([min(base_result[i],(input_array[i + 1] - base_val) % M + 1)
	for i in range(len(input_array)-1)])

print min([count_2(base_val, input_array, M) for base_val in range(M + 1)[1:]])

Submission status: Time Limit Exceeded

Solution code:
input_line_1 = raw_input()
input_line_2 = raw_input()
#N = int(input_line_1)
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)])
	
print min([count(base_val, input_array, M) for base_val in range(M + 1)[1:]])

Submission status: Time Limit Exceeded

Solution code:
input_line_1 = raw_input()
input_line_2 = raw_input()
#N = int(input_line_1)
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):
	diff_array = [(input_array[i + 1] - input_array[i]) % M for i in range(len(input_array) - 1)]
	diff_array_from_button = [(num - base_val) % M + 1 for num in input_array[1:]]
	return sum([min(diff_array[i],diff_array_from_button[i]) for i in range(len(diff_array))])

print min([count(base_val, input_array, M) for base_val in range(M + 1)[1:]])

Submission status: Time Limit Exceeded

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(("i=0;"+"D[i]+=D[i-1];i+=1;"*l)*2);print(S-l-max(D[a]+D[a+m]for a in A))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [n, m] = [int(input_raw[0]), int(input_raw[1])]
    input_raw = list(read_func().strip().split())
    min_cost = sys.maxint
    for i in range(m):
        x = i + 1
        cost = 0
        for j in range(n - 1):
            now = int(input_raw[j])
            target = int(input_raw[j + 1])
            if now < target:
                if x < target:
                    cost += min( (target - now),  1 +(target - x))
                elif x > target:
                    cost += min( (target - now), 1 + (m + target - x))
                else:
                    cost += 1
            elif now > target:
                if x < target:
                    cost += min((m + target - now),  1 +(target - x))
                elif x > target:
                    cost += min((m + target - now), 1 + (m + target - x))
                else:
                    cost += 1
        #print cost
        if cost < min_cost:
            min_cost = cost

    print min_cost


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N,M = map(int,input().split())
A = tuple(map(lambda x:int(x)-1,input().split()))

A = [a for a,b in zip(A,A[1:]) if a != b]+[A[-1]]


def it():
    events = [(a+1,-1) for a in A[:-1]] + [(a,p+1) for p,a in zip(A,A[1:])]
    events.sort()
    discount = 0
    cnt = 0
    for a,b in zip(A,A[1:]):
        discount += max2(0, (b-a)%M - 1 - b)
        cnt += int(b < a)
    yield discount
    last = 0
    for a,p in events:
        discount += (a-last)*cnt
        yield discount
        if p < 0:
            cnt += 1
        else:
            cnt -= 1
            discount -= (a-p)%M
        last = a

    yield discount

total = sum((b-a)%M for a,b in zip(A,A[1:]))
print(total - max(it()))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())        # N = 配列サイズ
A = list(map(int, input().split()))
imos = [0]*(2*M+1)
imos2 = [0]*(2*M+1)
res = 0
for i in range(N-1):
    a, b =A[i]-1, A[i+1]-1
    if a>b: b += M
    res += b-a
    if a+2>=b+1:
        continue
    imos[a+2] += 1
    imos[b+1] -= 1
    imos2[b+1] -= (b-a-1)
P = [0]
l = 0
for k, s in zip(imos, imos2):
    l += k
    P.append(P[-1] + l + s)
Q = P[1:-1]
R = [x+y for x, y in zip(Q[:M],Q[M:])]
print(res - max(R))

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,M = MI()
a = LI()

count = 0  # 順送りボタンだけを用いたときのボタンを押す回数
X = [0]*(2*M+1)
Y = [0]*(2*M+1)
# (X[0]+…+X[i])*i+(Y[0]+…+Y[i]) = お気に入りボタンをiに設定した時に、ボタンの押す回数を何回節約できるか

for i in range(N-1):
    a0,a1 = a[i],a[i+1]
    count += (a1-a0) % M
    if a0 > a1:
        a1 += M
    if a0 == a1:
        continue
    X[a0+2] += 1
    X[a1+1] -= 1
    Y[a0+2] -= a0+1
    Y[a1+1] += a0+1

from itertools import accumulate

X = list(accumulate(X))
Y = list(accumulate(Y))

A = [0]*(M+1)
for i in range(1,M+1):
    A[i] = (X[i]*i+Y[i]) + (X[i+M]*(i+M)+Y[i+M])

print(count-max(A))

Submission status: Accepted

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

imos = [0] * (2*m+2)
ans = 0
for i in range(n-1):
    a0 = a[i]-1
    a1 = a[i+1]-1
    dif = (a1-a0)%m
    ans += dif
    if(dif>=2):
        imos[a0+2] += 1
        imos[a0+dif+1] -= dif
        imos[a0+dif+2] += dif-1

# print(imos)

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

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

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

ans -= max(imos[:m])
print(ans)

Submission status: Accepted

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

ex = [0] * m
left = [0] * (2*m)
right = [[0,0] for _ in range(2*m)]

ans = 0
for i in range(n-1):
    a0 = a[i]-1
    a1 = a[i+1]-1
    ans += (a1-a0)%m
    left[a0+1] += 1
    right[a1 + (a0>a1)*m][0] += 1
    right[a1 + (a0>a1)*m][1] += (a1-a0)%m -1

now = left[0]
dif = 0
for i in range(1,2*m):
    dif += now
    ex[i%m] -= dif
    now += left[i] - right[i][0]
    dif -= right[i][1]

ans += min(ex)
print(ans)

Submission status: Accepted

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

n, m = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

cnt0 = [0] * m
cnt1 = [0] * m
for i in range(n-1):
    cnt0[a[i+1]] += (a[i+1] - a[i]) % m - 1
    if (a[i] + 1) % m <= a[i+1]:
        cnt1[(a[i]+1) % m] += 1
        cnt1[a[i+1]] -= 1
    else:
        cnt1[(a[i]+1) % m] += 1
        cnt1[0] += 1
        cnt1[a[i+1]] -= 1
cnt1 = list(accumulate(cnt1))
diff = list(accumulate([0] + [cnt0[i] - cnt1[i] for i in range(m-1)]))
ans = min(diff)
for i in range(n-1):
    ans += min((a[i+1] - a[i]) % m, a[i+1] + 1)
print(ans)

Submission status: Accepted

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

n, m = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

cnt0 = [0] * m
cnt1 = [0] * m
for i in range(n-1):
    cnt0[a[i+1]] += (a[i+1] - a[i]) % m - 1
    if (a[i] + 1) % m <= a[i+1]:
        cnt1[(a[i]+1) % m] += 1
        cnt1[a[i+1]] -= 1
    else:
        cnt1[(a[i]+1) % m] += 1
        cnt1[0] += 1
        cnt1[a[i+1]] -= 1
cnt1 = list(accumulate(cnt1))
ans = float('inf')
tmp = 0
for i in range(n-1):
    tmp += min((a[i+1] - a[i]) % m, a[i+1] + 1)
ans = tmp
for i in range(m-1):
    tmp += cnt0[i] - cnt1[i]
    ans = min(ans, tmp)
print(ans)

Submission status: Accepted

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

class BIT:
    def __init__(self, size):
        self.bit = [0] * (size + 1)
        self.size = size

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

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

n, m = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

bit0 = BIT(m)
bit1 = BIT(m)
for i in range(n-1):
    x, y = a[i], a[i+1]
    bit1.add(0, (y - x) % m)
    if (y - x) % m < 2:
        continue
    x = (x + 2) % m
    if x <= y:
        bit0.add(x, -1)
        bit1.add(x, x - 1)
        bit0.add(y + 1, 1)
        bit1.add(y + 1, -(x - 1))
    else:
        bit0.add(x, -1)
        bit1.add(x, x - 1)

        b = (0 - (x - 1)) % m
        bit0.add(0, -1)
        bit1.add(0, -b)
        bit0.add(y + 1, 1)
        bit1.add(y + 1, b)

ans = min(bit0.sum(i) * i + bit1.sum(i) for i in range(m))
print(ans)

Submission status: Accepted

Solution code:
def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N, M = LI()
    A = LI()
    S = [0]*(M+2)
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        S[a0+1] += 1
        S[a1] -= 1
        if a1<a0:
            S[0] += 1
    #print(S)
    for i in range(M):
        S[i+1] += S[i]
    for i in range(M+1):
        if S[i]<0:
            S[i] = 0
    D = defaultdict(int)
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        cost = (a1 + M - a0) % M - 1
        D[a1] += cost
    start = 0
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        cost = min(a1, (a1+M-a0)%M)
        start += cost
    #print(S)
    #print(D)
    #print(start)
    cost = start
    ans = start
    for i in range(1,M):
        cost += (D[i] - S[i])
        #print(cost)
        if ans>cost:
            ans = cost
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""