Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
flush = sys.stdout.flush

d = {"V":0, "M":1, "F":2}
def check(i):
    print(i)
    flush()
    s = input()
    if s[0] == "V":
        exit()
    return d[s[0]]

n = int(input())
left = 0
right = n-1
ls = check(left)
rs = check(right)

while right-left > 1:
    mid = (right+left)//2
    if check(mid) == ls:
        left = mid
    else:
        right = mid
raise

Fixed submission:
import sys
flush = sys.stdout.flush

d = {"M":0, "F":1}
def check(i):
    print(i)
    flush()
    s = input()
    if s[0] == "V":
        exit()
    return d[s[0]]

n = int(input())
left = 0
right = n-1
ls = check(left)
rs = check(right)

while right-left > 1:
    mid = (right+left)//2
    c = check(mid)
    if (c+mid-left)%2 == ls:
        left = mid
        ls = c
    else:
        right = mid

Buggy python submission (verdict: Time Limit Exceeded):
import sys
flush = sys.stdout.flush

d = {"V":0, "M":1, "F":2}
def check(i):
    print(i)
    flush()
    s = input()
    if s[0] == "V":
        exit()
    return d[s[0]]

n = int(input())
left = 0
right = n-1
ls = check(left)
rs = check(right)

while right-left > 1:
    mid = (right+left)//2
    if check(mid) == ls:
        left = mid
    else:
        right = mid

Fixed submission:
import sys
flush = sys.stdout.flush

d = {"M":0, "F":1}
def check(i):
    print(i)
    flush()
    s = input()
    if s[0] == "V":
        exit()
    return d[s[0]]

n = int(input())
left = 0
right = n-1
ls = check(left)
rs = check(right)

while right-left > 1:
    mid = (right+left)//2
    c = check(mid)
    if (c+mid-left)%2 == ls:
        left = mid
        ls = c
    else:
        right = mid
Buggy python submission (verdict: Runtime Error):
import itertools
n = int(input())
f = []
for i in range(n):
    f.append(list(map(int, input().split())))
p = []
for i in range(n):
    p.append(list(map(int, input().split())))

a = [i for i in range(10)]
combi = []
for i in range(10):
    combi.extend(list(itertools.combinations(a,i+ 1)))
#print(combi)

ans =  - float("inf")
for i in combi:
    #print(i)
    cnt = [0]*10
    for j in i:
        for k in range(n):
            cnt[k] += f[k][j]
    profit = sum([p[k][cnt[k]] for k in range(n)])
    ans = max(ans, profit)
print(ans)

Fixed submission:
import itertools
n = int(input())
f = []
for i in range(n):
    f.append(list(map(int, input().split())))
p = []
for i in range(n):
    p.append(list(map(int, input().split())))

a = [i for i in range(10)]
combi = []
for i in range(10):
    combi.extend(list(itertools.combinations(a,i+ 1)))
#print(combi)

ans =  - float("inf")
for i in combi:
    #print(i)
    cnt = [0]*n
    for j in i:
        for k in range(n):
            cnt[k] += f[k][j]
    profit = sum([p[k][cnt[k]] for k in range(n)])
    ans = max(ans, profit)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def LI(): return list(map(int, input().split()))
def LS(): return input().split()
def I(): return int(input())
def S(): return input()

n, c = LI()
l = []
for i in range(n):
    l.append(LI())

start = 0
end = 0
ans = 0
l.sort(key=lambda x: x[1])
#print(l)
while(len(l) > 0):
    ans += 1
    start = l[0][0]
    end = l[0][1]
    l = l[1:]
    if len(l) < 1:
        break
    remove_ind = []
    for ind, i in enumerate(l):
        if i[0] > end:
            start = i[0]
            end = i[1]
            remove_ind .append(ind)
    l = [l[i] for i in range(len(l)) if i not in remove_ind]
print(ans)


Fixed submission:
def LI(): return list(map(int, input().split()))
def LS(): return input().split()
def I(): return int(input())
def S(): return input()

n, c = LI()
l = []
for i in range(n):
    l.append(LI())

#チャンネル見る必要がある
#同じチャンネルで連続しているものはくっつける
la = [[[], []] for i in range(c)]
for i in l:
    la[i[2] - 1][0].append(i[0])
    la[i[2] - 1][1].append(i[1])

starts = []
ends = []
for s, e in la:
    wa = set(s).union(set(e))
    seki = set(s).intersection(set(e))
    a = list(wa.difference(seki))
    a.sort()
    for i, j in zip(a[0::2], a[1::2]):
        starts.append(i)
        ends.append(j)

s = min(starts)
e = max(ends)

imos = [0 for i in range(s,e + 2)]
for i, j in zip(starts, ends):
    imos[i - s] += 1
    imos[j - s + 1] -= 1
for i in range(len(imos) - 1):
    imos[i + 1] += imos[i]

print(max(imos))
Buggy python submission (verdict: Time Limit Exceeded):
# N < 90なのでテーブルにする必要ある？
def L(i):
    if i == 0:
        return 2
    elif i == 1:
        return 1
    else:
        return L(i- 1) + L(i-2)

s = int(input())
print(L(s))


Fixed submission:
# N < 90なのでテーブルにする必要ある？
table = [0]*90
def L(i):
    if i == 0:
        table[i] = 2
    elif i == 1:
        table[i] = 1
    else:
        table[i] = table[i- 1] + table[i-2]

s = int(input())
for i in range(s + 1):
    L(i)
print(table[s])
# tleした
Buggy python submission (verdict: Runtime Error):
N = int(input())
ue = list(set(list(map(int, input().split()))))
mid = list(set(list(map(int, input().split()))))
bot = list(set(list(map(int, input().split()))))
ue.sort()
mid.sort()
bot.sort()

#高速化できるのがキャッシュしか無い

ans = 0
pos_j = 0
for i in ue:
    flag = 0
    while(mid[pos_j] <= i):
        pos_j += 1
        if pos_j >= len(mid):
            flag = 1
            break
    if flag == 1:
        break

    pos_k = 0
    for j in range(pos_j, len(mid)):
        flag_ = 0
        while(bot[pos_k] <= mid[j]):
            pos_k += 1
            if pos_k >= len(bot):
                flag_ = 1
        if flag_ == 1:
            break
        ans += len(bot) - pos_k

    if flag_ == 1:
        break
    
print(ans)


Fixed submission:
import bisect

#動的計画法だった
N = int(input())
ue = (list(map(int, input().split())))
mid = (list(map(int, input().split())))
bot = (list(map(int, input().split())))
ue.sort()
mid.sort()
bot.sort()

ans = 0
for i in mid:
    ans += bisect.bisect_left(ue, i) * (len(bot) - bisect.bisect_right(bot, i))
print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
ue = list(set(list(map(int, input().split()))))
mid = list(set(list(map(int, input().split()))))
bot = list(set(list(map(int, input().split()))))
ue.sort()
mid.sort()
bot.sort()

#高速化できるのがキャッシュしか無い

ans = 0
pos_j = 0
for i in ue:
    flag = 0
    while(mid[pos_j] <= i):
        pos_j += 1
        if pos_j >= len(mid):
            flag = 1
            break
    if flag == 1:
        break

    pos_k = 0
    for j in range(pos_j, len(mid)):
        flag_ = 0
        while(bot[pos_k] <= mid[j]):
            pos_k += 1
            if pos_k >= len(bot):
                flag_ = 1
        if flag_ == 1:
            break
        ans += len(bot) - pos_k
print(ans)


Fixed submission:
import bisect

#動的計画法だった
N = int(input())
ue = (list(map(int, input().split())))
mid = (list(map(int, input().split())))
bot = (list(map(int, input().split())))
ue.sort()
mid.sort()
bot.sort()

ans = 0
for i in mid:
    ans += bisect.bisect_left(ue, i) * (len(bot) - bisect.bisect_right(bot, i))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
INF = 10**9
a = [[INF]*n for i in range(n)]
hen_m = []
for i in range(m):
    x1, x2 = map(int, input().split())
    x1 -= 1
    x2 -= 1
    hen_m.append([x1, x2])
    a[x1][x2] = 1
    a[x2][x1] = 1
for i in range(n):
    a[i][i] = 0

#ワーシャルフロイド
def warshall(n, c):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c[j][k] = min(c[j][k], c[j][i] + c[i][k])

ans = 0
# Mの辺を消して、わ～シャルフロイド
for i in range(m):
    b = [i[::] for i in a]
    x1 , x2 = hen_m[i]
    b[x1][x2] = INF
    b[x2][x1] = INF
    warshall(n, b)
    flag = 0
    for j in range(n - 1):
        for k in range(j + 1,n):
            if b[j][k] >= INF:
                flag = 1
                break
        if flag == 1:
            break
    #print(i, flag)
    ans += flag
print(ans)


Fixed submission:
n, m = map(int, input().split())
a = [[False]*n for i in range(n)]
hen_m = []
for i in range(m):
    x1, x2 = map(int, input().split())
    x1 -= 1
    x2 -= 1
    hen_m.append([x1, x2])
    a[x1][x2] = True
    a[x2][x1] = True
for i in range(n):
    a[i][i] = True

#ワーシャルフロイド
def warshall(n, c):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                c[j][k] = c[j][k] or (c[j][i] and c[i][k])

ans = 0
# Mの辺を消して、わ～シャルフロイド
for i in range(m):
    b = [i[::] for i in a]
    x1 , x2 = hen_m[i]
    b[x1][x2] = False
    b[x2][x1] = False
    warshall(n, b)
    flag = 0
    for j in range(n - 1):
        for k in range(j + 1,n):
            if not b[j][k]:
                flag = 1
                break
        if flag == 1:
            break
    #print(i, flag)
    ans += flag
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
for i in range(1,3501):
    for j in range(i, 3501):
        top = n*i*j
        bot = 4*i*j - n*(i+j)
        if bot > 0 and top >= bot and top%bot == 0:
            w = top//bot
            if w >= j:
                print(i, j, w)
                exit()

Fixed submission:
n = int(input())
for i in range(1,3501):
    for j in range(i, 3501):
        top = n*i*j
        bot = 4*i*j - n*(i+j)
        if bot > 0 and top%bot == 0:
            w = top//bot
            if w > 0:
                print(i, j, w)
                exit()
Buggy python submission (verdict: Runtime Error):
for k in range(n):
    for i in range(n):
        for j in range(n):
            if a[i][k] + a[k][j] < a[i][j]:
                print(-1)
                exit()
            elif a[i][k] + a[k][j] == a[i][j] and i!=k!=j:
                b[i][j] = 0

ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j]:
            ans += a[i][j]
print(ans//2)

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

for i in range(n):
    for j in range(n):
        for k in range(n):
            if a[i][k] + a[k][j] < a[i][j]:
                print(-1)
                exit()
            elif a[i][k] + a[k][j] == a[i][j] and i!=k!=j:
                b[i][j] = 0

ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j]:
            ans += a[i][j]
print(ans//2)
Buggy python submission (verdict: Runtime Error):
n = int(input())
ans = 0
for i in range(n):
    a, b = list(map(int, input().split))
    ans = b - a +1
print(ans)

Fixed submission:
n = int(input())
ans = 0
for i in range(n):
    a, b = list(map(int, input().split()))
    ans += b - a +1
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = []
for i in range(n):
    a.append(int(input())
ans = 0
for i in set(a):
    if i in a:
        ans += 1
print(ans)

Fixed submission:
n = int(input())
a = {}
for i in range(n):
    b = int(input())
    if b in a.keys():
        a[b] += 1
    else:
        a[b] = 1
ans = 0
for i in a.keys():
    if a[i]%2 == 1:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
c = []
for i in range(n):
    a = int(input())
    if a in c:
        c.pop(c.index(a))
    else:
        c.append(a)
print(len(c))

Fixed submission:
n = int(input())
a = {}
for i in range(n):
    b = int(input())
    if b in a.keys():
        a[b] += 1
    else:
        a[b] = 1
ans = 0
for i in a.keys():
    if a[i]%2 == 1:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = [0 for i in range(1000000000)]
for i in range(n):
    a[int(input()) + 1] += 1
ans = 0
for i in a:
    if i%2 == 1:
        ans += 1
print(ans)

Fixed submission:
n = int(input())
a = {}
for i in range(n):
    b = int(input())
    if b in a.keys():
        a[b] += 1
    else:
        a[b] = 1
ans = 0
for i in a.keys():
    if a[i]%2 == 1:
        ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m, r = map(int,input().split())
rs = list(map(int, input().split()))
distance = [[float("inf")]*n for i in range(n)]
for i in range(n):
    distance[i][i] = 0
for i in range(m):
    a, b, c = list(map(int, input().split()))
    a, b = a-1, b-1
    distance[a][b] = c
    distance[b][a] = c

# 全点間最短距離を求める
for k in range(n):
    for i in range(n):
        for j in range(n):
            distance[i][j] = min(distance[i][j],distance[i][k] + distance[k][j])
# r個の並びを考える
from itertools import permutations
ans = float("inf")

for v in permutations(rs, len(rs)):
    dist_tmp = 0
    for i in range(r-1):
        dist_tmp += distance[v[i]-1][v[i+1]-1]
    ans = min(ans, dist_tmp)
print(ans)

Fixed submission:
from scipy.sparse.csgraph import floyd_warshall

n, m, r = map(int,input().split())
rs = list(map(int, input().split()))
edge = [[0]*n for i in range(n)]
for i in range(m):
    a, b, c = list(map(int, input().split()))
    a, b = a-1, b-1
    edge[a][b] = c
    edge[b][a] = c
dist = floyd_warshall(edge, directed=False)

from itertools import permutations
ans = float("inf")
    
for v in permutations(rs, len(rs)):
    dist_tmp = 0
    for i in range(r-1):
        dist_tmp += dist[v[i]-1][v[i+1]-1]
    ans = min(ans, int(dist_tmp))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = list(map(int, input().split()))

b = [i - 1 for i in a]
c = [i + 1 for i in a]

a.extend(b)
a.extend(c)
f = set(a)
ans = 0
for i in f:
    ans = max(ans, a.count(i))

print(ans)


Fixed submission:
N = int(input())
a = list(map(int, input().split()))

N = 10**5
cnt = [0 for i in range(N+2)]
# index 0 == -1
for i in a:
    cnt[i] += 1
    cnt[i+1] += 1
    cnt[i+2] += 1

print(max(cnt))
Buggy python submission (verdict: Runtime Error):
N = int(input())
p = list(map(int, input().split()))

count = 0
now = 0
for i in range(len(p)):
    if len(p) == 0:
        break
    if now+1 == p[0]:
        p.pop(0)
        count += 1
        now += 1
    p.pop(0)
    now += 1
print(count)


Fixed submission:
N = int(input())
p = list(map(int, input().split()))

count = 0
now = 0
for i in range(len(p)):
    if len(p) == 0:
        break
    if now+1 == p[0]:
        p.pop(0)
        count += 1
        now += 1
    if len(p) == 0:
        break
    p.pop(0)
    now += 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = [i + 1 for i in a]
c = [i - 1 for i in a]
use_set = set(a) | set(b) | set(c)
ans = 0
for i in use_set:
    ans = max(ans, a.count(i) + b.count(i) + c.count(i))
print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

"""
b = [i + 1 for i in a]
c = [i - 1 for i in a]
use_set = set(a) | set(b) | set(c)
ans = 0
for i in use_set:
    ans = max(ans, a.count(i) + b.count(i) + c.count(i))
print(ans)
"""
#これだと最後でTLE
#inの段階でhash?

ans = {}
for i in a:
    for j in range(3):
        if i + j - 1 not in ans:
            ans[i + j - 1] = 1
        else:
            ans[i + j - 1] += 1

print(max(ans.values()))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

use_1 = 0
use_2 = 0
for i in set(a):
    can = a.count(i) // 2
    if can == 1:
        if use_1 < i:
            use_2 = use_1
            use_1 = i
    elif can > 1:
         use_1 = max(use_1, i)
         use_2 = max(use_2, i)

print(use_1*use_2)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
tobasu = 0
one = 0
two = 0
for i in range(len(a) - 1):
    if tobasu == 1:
        tobasu = 0
        continue
    if a[i] == a[i + 1] and one == 0:
        tobasu = 1
        one = a[i]
    elif a[i] == a[i + 1] and one != 0 and two == 0:
        two = a[i]
        break
print(one * two)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

use = []
for i in set(a):
    can = a.count(i) // 2
    if can > 0:
        for j in range(can):
            use.append(i)
use.sort()
if len(use) > 1:
    print(use[-1] * use[-2])
else:
    print(0)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
tobasu = 0
one = 0
two = 0
for i in range(len(a) - 1):
    if tobasu == 1:
        tobasu = 0
        continue
    if a[i] == a[i + 1] and one == 0:
        tobasu = 1
        one = a[i]
    elif a[i] == a[i + 1] and one != 0 and two == 0:
        two = a[i]
        break
print(one * two)
Buggy python submission (verdict: Time Limit Exceeded):
a = list(map(lambda x: ord(x)-ord("a"), list(input())))
n = len(a)
m = 26

b = [None]*(n+m)
prev = [0]*m
for i in range(m):
    b[n+i] = (1, (i,))
    prev[i] = n+i

for i in reversed(range(n)):
    ai = a[i]
    tmp = min(b[j] for j in prev)
    b[i] = (tmp[0]+1, (ai,)+tmp[1])
    prev[ai] = i
tmp = min(b[j] for j in prev)
ans = "".join(chr(ord("a")+i) for i in tmp[1])
print(ans)

Fixed submission:
a = list(map(lambda x: ord(x)-ord("a"), list(input())))
n = len(a)
m = 26

b = [1]*(n+1)
prev = [n]*m
G = [[] for i in range(n+1)]
for i in reversed(range(n)):
    ai = a[i]
    tmp = min(b[j] for j in prev)
    for j in prev:
        G[i].append(j)
    b[i] = tmp+1
    prev[ai] = i

cnt = min(b[j] for j in prev)
edge = prev
ans = []
for _ in range(cnt):
    for i, to in enumerate(edge):
        if b[to] == cnt-_:
            ans.append(chr(ord("a")+i))
            edge = G[to]
            break
print("".join(ans))
Buggy python submission (verdict: Runtime Error):
    def gcd(a, b):
        if a < b:
            a, b = b, a
        if b == 0:
            return a
        else:
            return int(gcd(b, a%b))
     
    def lcm(a, b):
        return int(a // gcd(a, b) * b)
     
    N = input()
    V = 1
    for i in range(int(N)):
        T = input()
        V = lcm(V, int(T))
     
    print("%d" % V)

Fixed submission:
from fractions import gcd

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))
# 最小公倍数が欲しい
ans = 1
for i in T:
    ans = int(ans * i //gcd(ans, i))
print(ans)
Buggy python submission (verdict: Runtime Error):
def dfs_rec(start, cost, aa, bb, cc):
    use_index = []
    for i in range(aa.count(start)):
        use_index.append(aa.index(start))
    for i in range(bb.count(start)):
        use_index.append(bb.index(start))
    use_index = sorted(use_index)[::-1]
    # この点から行けるところがないとき
    if len(use_index) == 0:
        return
    for i in use_index:
        p = aa[i] if bb[i] == start else bb[i]
        DP_modoki[p-1] = cc[i] + cost
        aa.pop(i)
        bb.pop(i)
        cc.pop(i)
        dfs_rec(p, DP_modoki[p-1], aa, bb, cc)


# ダイクストラとDP?
#ある頂点pからKまでの最短距離のリストがあれば良い?
# 結局Q個その都度検索したほうが早いか?
# 意地悪なサンプルでTLEするかも
N = int(input())
a, b, c = [], [], []
for i in range(N-1):
    s1, s2, s3 = list(map(int, input().split()))
    a.append(s1)
    b.append(s2)
    c.append(s3)
Q, K = list(map(int, input().split()))
x, y = [], []
for i in range(Q):
    s1, s2 = list(map(int, input().split()))
    x.append(s1)
    y.append(s2)
# Kまでの最短距離が必要な頂点のリスト
keisan_list = list(set(x).intersection(set(y)))
# 0からN-1に注意
DP_modoki = [0 for _ in range(N)]

#ここからDP?→ではなく、深さ優先探索で全探索
# 閉路がないなら、辿っていけば最短距離?
dfs_rec(K, 0, a, b, c)
for i in range(Q):
    print(DP_modoki[x[i]-1] + DP_modoki[y[i]-1])


Fixed submission:
import heapq

G = [{}]

def setNode(n):
  global G
  G = [{} for i in range(n)]
def solve(s, n):
  global G
  fixed = [None]*n
  q = []
  heapq.heappush(q, (0,s))
  while q:
    w,x = heapq.heappop(q)
    if fixed[x] is not None: continue
    fixed[x] = w
    for y in G[x]:
        if fixed[y] is None:
            heapq.heappush(q, (w + G[x][y], y))
  return fixed


n = int(input())
setNode(n)
for i in range(n-1):
  s,t,w = map(int,input().split())
  G[s-1][t-1] = w
  G[t-1][s-1] = w
Q, K = map(int, input().split())
dist = solve(K-1,n)
for i in range(Q):
    x, y = map(int,input().split())
    print(dist[x-1]+dist[y-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
start = []
end = []
for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1 or b == 1:
        start.append(a*b)
    if a == N or b == N:
        end.append(a * b / N)
flag = 0
for i in start:
    if i in end:
        print("POSSIBLE")
        flag = 1
        break
if not(flag):
    print("IMPOSSIBLE")


Fixed submission:
N, M = list(map(int, input().split()))
start = set([])
end = set([])
for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1 or b == 1:
        start.add(a*b)
    if a == N or b == N:
        end.add(a * b / N)
flag = 0
for i in start:
    if i in end:
        print("POSSIBLE")
        flag = 1
        break
if not(flag):
    print("IMPOSSIBLE")

Buggy python submission (verdict: Time Limit Exceeded):
N, M = list(map(int, input().split()))
start = []
end = []
for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1 or b == 1:
        start.append(a*b)
    if a == N or b == N:
        end.append(a * b / N)
flag = 0
for i in start:
    if i in end:
        flag = 1

if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


Fixed submission:
N, M = list(map(int, input().split()))
start = set([])
end = set([])
for i in range(M):
    a, b = list(map(int, input().split()))
    if a == 1 or b == 1:
        start.add(a*b)
    if a == N or b == N:
        end.add(a * b / N)
flag = 0
for i in start:
    if i in end:
        print("POSSIBLE")
        flag = 1
        break
if not(flag):
    print("IMPOSSIBLE")
Buggy python submission (verdict: Time Limit Exceeded):
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)

Fixed submission:
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)