Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

s=input()
x,y=map(int,input().split())

lf = [0]
tf = 0
for i in range(len(s)):
    if s[i] =="F":
        lf[tf] += 1
    else:
        lf.append(0)
        tf += 1

lx = [lf[i] for i in range(len(lf)) if i % 2 == 0]
ly = [lf[i] for i in range(len(lf)) if i % 2 == 1]
start =lx.pop(0)
dpx = [[False for _ in range(20000)] for _ in range(len(lx)+1)]
dpx[0][start+10000] = True
for i in range(len(lx)):
    for j in range(20000):
        if j-lx[i] >= 0:
            dpx[i+1][j] = dpx[i][j-lx[i]]
        if j+lx[i] < 20000:
            dpx[i+1][j] = dpx[i+1][j] or dpx[i][j+lx[i]]

dpy = [[False for _ in range(20000)] for _ in range(len(ly)+1)]
dpy[0][10000] = True
for i in range(len(ly)):
    for j in range(20000):
        if j-ly[i] >= 0:
            dpy[i+1][j] = dpy[i][j-ly[i]]
        if j+ly[i] < 20000:
            dpy[i+1][j] = dpy[i+1][j] or dpy[i][j+ly[i]]

if dpx[-1][x+10000] and dpy[-1][y+10000]:print("Yes")
else:print("No")

### FIXED CODE ###


def main():
    s=input()
    x,y=map(int,input().split())

    lf = [0]
    tf = 0
    for i in range(len(s)):
        if s[i] =="F":
            lf[tf] += 1
        else:
            lf.append(0)
            tf += 1

    lx = [lf[i] for i in range(len(lf)) if i % 2 == 0]
    ly = [lf[i] for i in range(len(lf)) if i % 2 == 1]
    dpxcenter = sum(lx)
    if abs(x)>dpxcenter: return "No"
    dpxedge = dpxcenter*2+20
    dpx = [[False for _ in range(dpxedge)] for _ in range(len(lx)+1)]
    dpx[1][dpxcenter+lx[0]+10] = True
    for i in range(1,len(lx)):
        for j in range(dpxedge):
            if j-lx[i] >= 0:
                dpx[i+1][j] = dpx[i][j-lx[i]]
            if j+lx[i] < dpxedge:
                dpx[i+1][j] = dpx[i+1][j] or dpx[i][j+lx[i]]

    dpycenter = sum(ly)
    if abs(y)>dpycenter: return "No"
    dpyedge = dpycenter*2+20
    dpy = [[False for _ in range(dpyedge)] for _ in range(len(ly)+1)]
    dpy[0][dpycenter+10] = True
    for i in range(len(ly)):
        for j in range(dpyedge):
            if j-ly[i] >= 0:
                dpy[i+1][j] = dpy[i][j-ly[i]]
            if j+ly[i] < dpyedge:
                dpy[i+1][j] = dpy[i+1][j] or dpy[i][j+ly[i]]

    if dpx[-1][x+dpxcenter+10] and dpy[-1][y+dpycenter+10]:return "Yes"
    else:return "No"

print(main())
### BUGGY CODE ###

n,p = map(int,input().split())
if n == 1:
    print(p)
    exit()
i =1
while i**n <= p:
    if p%(i**n)==0:
        ans = i
    i += 1
print(ans)

### FIXED CODE ###

n,p = map(int,input().split())
if n == 1:
    print(p)
    exit()
if n >=40:
    print(1)
    exit()
i =2
ans =1
while i**n <= p:
    if p%(i**n)==0:
        ans *= i
        p =p//(i**n)

    else:
        i += 1
print(ans)
### BUGGY CODE ###

from math import *
N=int(input())
"""
l=[]
pf={}
m=N
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
print(l)
"""
a=1
while True:
    t=sqrt(1+8*a*N)
    if (pow(int(sqrt(1+8*a*N)),2)==1+8*a*N)and(int(t)%2==1):
        print((-1+int(t))//2)
        break
    a=a+1


### FIXED CODE ###

from math import sqrt
from collections import deque
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
N=int(input())
def gcd_ext(a, b):
    x, y, lastx, lasty = 0, 1, 1, 0
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, y, lastx, lasty = lastx - q * x, lasty - q * y, x, y
    return (lastx, lasty)
l=[]
pf={}
m=N*2
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
#print(pf)
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)
d=deque()
d.append([])

for i in range(len(l)):
    x=list(range(values[i]+1))
    d2 = deque()
    #print(x)
    while len(d)>0:
        l=d.popleft()
        for j in x:
            l2=l[:]
            l2.append(j)
            d2.append(l2)
    d=d2
    #print(d)
ans=float("inf")
x=0
y=0
while len(d)>0:
    l=d.popleft()
    num=1
    res=1
    for i in range(len(l)):
        num=num*pow(keys[i],l[i])
        res=res*pow(keys[i],values[i]-l[i])
    #print(num,res)
    #x*num=k+1のときを考える
    if ggcd(num,res)==1:
        #x*num+y*res=1
        x,y=gcd_ext(num,res)
        if (x==0)or(y==0):
            x1=x+num*res
            y1=y+num+res
            ans=min(ans,x1*num-1)
            x2=x-num*res
            y2=x-num*res
            ans=min(ans,-x2*num)
        else:#どっちかは+でどっちかは-
            if x>y:
                ans=min(ans,x*num-1)
                x1=x-num*res
                ans=min(ans,-x1*num)
            else:
                x1=x+num*res
                ans=min(ans,x1*num-1)
                ans=min(ans,-x*num)
print(ans)
### BUGGY CODE ###

n,x,m = map(int, input().split()) 
ans = 0
x_list = []

for _ in range(min(10**5,n)):
    x_list.append(x)
    ans += x
    x = x**2 % m
    if x == 0:
        break
    if x == 1:
        ans = ans + (n-len(x_list))
        break
    if x_list.count(x) == 1:
        after_list = x_list[x_list.index(x):(len(x_list))]
        if x_list.index(x) == 0:
            if (n // len(x_list)) == 0:
                ans = ans * (n // len(x_list))
            else:
                ans = ans * (n // len(x_list)) + sum(x_list[0:((n % len(x_list)))])
        else:
            if (n-x_list.index(x)) % len(after_list) == 0:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(x_list[0:(x_list.index(x))])
            else:
                ans = (ans - sum(x_list[0:(x_list.index(x))])) * ((n-x_list.index(x)) // len(after_list)) + sum(after_list[0:(((n-x_list.index(x)) % len(after_list)))]) + sum(x_list[0:(x_list.index(x))])
        break

print(ans)

### FIXED CODE ###

N, X, M = map(int, input().split())
 
def next_f(a):
    return a * a % M
 
visited = [None] * M
sum_at_visit = [None] * M
loop_done = False
 
time = 1
ans = 0
x = X
while time <= N:
    if not loop_done and visited[x] is not None:
        # found cycle                                                                                                                                         
        loop_len = time - visited[x]
        loop_sum = ans + x - sum_at_visit[x]
        loops = (N-loop_len-time) // loop_len
        time += loop_len * loops
        ans += loop_sum * loops
        loop_done = True
    ans += x
    visited[x] = time
    sum_at_visit[x] = ans
    time += 1
    x = next_f(x)
print(ans)
### BUGGY CODE ###

n,p=map(int, input().split())
ans=1
m=int(pow(p,1/n))+1
if n==0:
    print(p)
else:
    m=int(pow(p,1/n))+1
    i=2
    c=0
    while(i<=p and i<=m):
        #print('i,p=',i,p)
        if p % i == 0:
            p=p/i
            c=c+1
            if p % i != 0:
                #print('i**(c//n)=',i**(c//n))
                ans = ans * ( i**(c//n) )
                i=i+1
                c=0
        else:
            i=i+1
    print(ans)


### FIXED CODE ###

n,p=map(int, input().split())
ans=1
m=int(pow(p,1/n))+1
if n==1:
    print(p)
else:
    m=int(pow(p,1/n))+1
    i=2
    c=0
    while(i<=p and i<=m):
        #print('i,p=',i,p)
        if p % i == 0:
            p=p/i
            c=c+1
            if p % i != 0:
                #print('i**(c//n)=',i**(c//n))
                ans = ans * ( i**(c//n) )
                i=i+1
                c=0
        else:
            i=i+1
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = max(max(a),max(b)).bit_length()+1
a = np.array(a,dtype=np.int32)
b = np.array(b,dtype=np.int32)
ans = 0
for i in range(1,x+1):
  c = a&(1<<i)-1
  d = b&(1<<i)-1
  d.sort()
  t = 1<<(i-1)
  anstmp = 0
  for j in range(n):
    y = c[j]
    t1 = np.searchsorted(d,t-y)
    t2 = np.searchsorted(d,2*t-y)
    t3 = np.searchsorted(d,3*t-y)
    anstmp += (t2-t1)+(n-t3)
  if anstmp%2:
    ans += t
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = max(max(a),max(b)).bit_length()+1
a = np.array(a,dtype=np.int32)
b = np.array(b,dtype=np.int32)
ans = 0
for i in range(1,x+1):
  c = a&(1<<i)-1
  d = b&(1<<i)-1
  d.sort()
  t = 1<<(i-1)
  anstmp = 0
  t1 = np.searchsorted(d,t-c).sum()
  t2 = np.searchsorted(d,2*t-c).sum()
  t3 = np.searchsorted(d,3*t-c).sum()
  anstmp += (t2-t1)+(n-t3)
  if anstmp%2:
    ans += t
print(ans)
### BUGGY CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
# import bisect
# import heapq # priolity-queue
# from time import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

# mod = int(1e9+7)
mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n,k = readInt()
    s = set()
    for i in range(k):
        l,r = readInt()
        for j in range(l,r+1):
            s.add(j)
    s = list(s)
    s.sort()
    dp = [0 for i in range(n)]
    dp[0] = 1
    for i in range(n):
        if dp[i]==-1:
            continue
        for j in range(len(s)):
            if i+s[j]>=n:
                break
            dp[i+s[j]] += dp[i]
            dp[i+s[j]] %= mod
    print(dp[n-1])
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

# import sys
# import math #sqrt,gcd,pi
# import decimal
# import queue # queue
import bisect
# import heapq # priolity-queue
# from time import time
# from itertools import product,permutations,\
    # combinations,combinations_with_replacement
# 重複あり順列、順列、組み合わせ、重複あり組み合わせ
# import collections # deque
# from operator import itemgetter,mul
# from fractions import Fraction
# from functools import reduce

# mod = int(1e9+7)
mod = 998244353
INF = 1<<50

def readInt():
    return list(map(int,input().split()))

def main():
    n,k = readInt()
    l = []
    r = []
    for i in range(k):
        a,b = readInt()
        l.append(a)
        r.append(b)
    dp = [0 for i in range(n+1)]
    dp[1] = 1
    dpsum = [0 for i in range(n+1)]
    dpsum[1] = 1
    for i in range(2,n+1):
        for j in range(k):
            lj = max(1,i - r[j])
            rj = i - l[j]
            if rj<1:
                continue
            dp[i] += dpsum[rj] - dpsum[lj-1]
            dp[i] %= mod
        dpsum[i] = dpsum[i-1] + dp[i]
    print(dp[n])
    return

if __name__=='__main__':
    main()
### BUGGY CODE ###

import numpy as np


def solve(n, aaa):
    if aaa[0] > 0:
        return -1
    if any(a1 - a0 > 1 for a0, a1 in zip(aaa, aaa[1:])):
        return -1
    ans = 0
    aaa.reverse()

    while any(aaa):
        new = [0] * (len(aaa) - 1)
        for i, (a1, a0) in enumerate(zip(aaa, aaa[1:])):
            if a1 == 0:
                continue
            ans += 1
            if a1 - a0 < 1:
                ap = a1
            else:
                ap = 0
            new[i] = max(ap - 1, new[i - 1] - 1, 0)
        aaa = np.trim_zeros(new) + [0]
    return ans


n = int(input())
aaa = list(map(int, (input() for _ in range(n))))
print(solve(n, aaa))


### FIXED CODE ###

def solve(n, aaa):
    if aaa[0] > 0:
        return -1
    if any(a1 - a0 > 1 for a0, a1 in zip(aaa, aaa[1:])):
        return -1
    ans = 0
    a0 = 0

    for a1 in aaa[1:]:
        if a1 - a0 != 1:
            ans += a0
        a0 = a1

    return ans + a0


n = int(input())
aaa = list(map(int, (input() for _ in range(n))))
print(solve(n, aaa))
### BUGGY CODE ###

class WarshallFroyd():
    def __init__(self, N):
        self.N = N
        self.d = [[float('inf')] * N for _ in range(N)]

    def add(self, u, v, c, directed=False):
        """
        Valid only for '0-indexed' graphs!
        add an edge from u to v with cost d
        """
        if directed == False:
            self.d[u][v] = c
            self.d[v][u] = c
        else:
            self.d[u][v] = c

    def WarshallFloyd_search(self):
        """
        Change self.d to self.d[i][j] = (minimal cost from i to j)
        If self.d[i][j] < 0, this graph has negative loops
        """
        for k in range(self.N):
            for i in range(self.N):
                for j in range(self.N):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        hasNegativeCycle = False
        for i in range(self.N):
            if self.d[i][i] < 0:
                hasNegativeCycle = True
                break
        for i in range(self.N):
            self.d[i][i] = 0
        return hasNegativeCycle, self.d



N, M, L = map(int, input().split())
graph = WarshallFroyd(N)
for _ in range(M):
    a, b, c = map(int, input().split())
    graph.add(a-1, b-1, c)
_, d = graph.WarshallFloyd_search()
#print('distance={}'.format(d))


graph2 = WarshallFroyd(N)
for a in range(N - 1):
    for b in range(a+1, N):
        if d[a][b] <= L:
            graph2.add(a, b, 1)
_, times = graph2.WarshallFloyd_search()
#print('times={}'.format(times))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    if times[s-1][t-1] != float('inf'):
        print(times[s-1][t-1] - 1)
    else:
        print(-1)


### FIXED CODE ###

inf = 10 ** 15

N, M, L = map(int, input().split())
dp = [[inf] * N for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
for i in range(N):
    dp[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
#print('distance={}'.format(dp))


dp2 = [[inf] * N for _ in range(N)]
for a in range(N - 1):
    for b in range(a+1, N):
        if dp[a][b] <= L:
            dp2[a][b] = 1
            dp2[b][a] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            dp2[i][j] = min(dp2[i][j], dp2[i][k] + dp2[k][j])
#print('times={}'.format(dp2))


Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    cost = dp2[s-1][t-1]
    if cost != inf:
        print(cost - 1)
    else:
        print(-1)
### BUGGY CODE ###

import math
n = int(input())
lis = list(map(int,input().split()))
ans = 0
num = [1 for i in range(10 ** 6 + 5)]
lis.sort()
for i in range(n):
  #     print(lis[i])
    key = 1
    gone = 1
    if i > 0:
        if lis[i] == lis[i-1]:
            key = 0
            gone = 0
    if i < n-1:
        if lis[i] == lis[i+1]:
            key = 0
    ans += num[lis[i]] * key
    num[lis[i]] = 0
    cnt = lis[i]
    t = 1
    if gone:
        while cnt*t <= 10 ** 6:
            num[cnt*t] = 0
            t += 1
print(ans)

### FIXED CODE ###

import math
n = int(input())
lis = list(map(int,input().split()))
ans = 0
num = [1 for i in range(10 ** 6 + 5)]
lis.sort()
for i in range(n):
  #     print(lis[i])
    key = 1
    gone = 1
    if i > 0:
        if lis[i] == lis[i-1]:
            key = 0
            gone = 0
    if i < n-1:
        if lis[i] == lis[i+1]:
            key = 0
    ans += num[lis[i]] * key
    num[lis[i]] = 0
    cnt = lis[i]
    t = 1
    if gone:
        while cnt*t <= 10 ** 6:
            num[cnt*t] = 0
            t += 1
print(ans)
### BUGGY CODE ###

import copy
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(b)]
s,t=map(int,input().split())
dd=[[]for i in range(a+1)]
for i in range(b):
  da=c[i][0]
  db=c[i][1]
  dd[da].append(db)
  
d=[[]for i in range(a+1)]
for i in range(a+1):
  for j in dd[i]:
    for k in dd[j]:
      for l in dd[k]:
        d[i].append(l)
e=[s]
f=[s]
h=0
for i in range(1,a+1):
  g=[]
  for j in f:
    for k in d[j]:
      if k not in e:
        e.append(k)
        g.append(k)
        if k==t:
          print(i)
          h=1
          break
    if h==1:
      break
  if h==1:
    break
  if g==[]:
    print(-1)
    break
  f=copy.copy(g)

### FIXED CODE ###

import copy
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(b)]
s,t=map(int,input().split())
s=3*s
t=3*t
dd=[[]for i in range(a+1)]
for i in range(b):
  da=c[i][0]
  db=c[i][1]
  dd[da].append(db)
  

d=[[]for i in range(3*(a+1))]
for i in range(len(dd)):
  for j in dd[i]:
      d[3*i].append(3*j+1)
      d[3*i+1].append(3*j+2)
      d[3*i+2].append(3*j)
e=[-1 for i in range(3*a+3)]
f=[s]
h=0
for i in range(1,3*a+3):
  g=[]
  for j in f:
    for k in d[j]:
      if e[k]==-1:
        e[k]=1
        g.append(k)
        if k==t:
          print(i//3)
          h=1
          break
    if h==1:
      break
  if h==1:
    break
  if g==[]:
    print(-1)
    break
  f=copy.copy(g)
### BUGGY CODE ###

import sys
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [set() for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].add(b)
        g[b].add(a)

    s = 1
    Q = deque([s])
    ans = k
    Qappend = Q.append
    searched = [0 for i in range(n+1)]
    searched[s] = 1
    while len(Q) != 0:
        v = Q.popleft()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            if cand == 0:
                print(0)
                return
            searched[i] = 1
            ans *= cand
            cand -= 1
            Qappend(i)
        ans = ans % MOD
    print(ans % MOD)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

K = int(input())
ans = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd(i, j, k)
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
K = int(input())
ans = 0
 
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd(i, j, k)
print(ans)
### BUGGY CODE ###


# -*- coding: utf-8 -*-
import random
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))

def warshall_floyd(g):
    d = g
    N = len(g)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


def slv():
    N, M, L = list(map(int, input().split()))
    g = [[sys.maxsize]*(N) for _ in range(N)]
    for i in range(N):
        g[i][i] = 0
    for _ in range(M):
        a, b, c = list(map(int, input().split()))
        if c > L:
            continue
        g[a-1][b-1] = c
        g[b-1][a-1] = c
    
    d = g
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    gg = [[sys.maxsize]*(N) for _ in range(N)]
    for u in range(N):
        for v in range(N):
            if d[u][v] <= L:
                gg[u][v] = 1
    
    d = gg
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    Q = read_int()
    for _ in range(Q):
        s, t = list(map(int, input().split()))
        c = d[s-1][t-1]
        if c != sys.maxsize:
            print(c-1)
        else:
            print(-1)



def main():
    slv()
    # N, M, L = read_int_n()
    # ABC = [read_int_n() for _ in range(M)]
    # Q = read_int()
    # ST = [read_int_n() for _ in range(Q)]
    
    # (slv(N, M, L, ABC, Q, ST))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def slove():
    import sys
    input = sys.stdin.readline
    n, m, l = list(map(int, input().rstrip('\n').split()))
    INF = 10 ** 11
    w = [[INF] * n for _ in range(n)]
    wl = [[INF] * n for _ in range(n)]

    for i in range(n):
        w[i][i] = 0

    for i in range(m):
        a, b, c = list(map(int, input().rstrip('\n').split()))
        if c <= l:
            w[a - 1][b - 1] = c
            w[b - 1][a - 1] = c

    for i in range(n):
        for j in range(n):
            for k in range(n):
                w[j][k] = min(w[j][k], w[j][i] + w[i][k])

    for i in range(n):
        for j in range(n):
            if w[i][j] <= l:
                wl[i][j] = 1
    for i in range(n):
        for j in range(n):
            for k in range(n):
                wl[j][k] = min(wl[j][k], wl[j][i] + wl[i][k])

    q = int(input().rstrip('\n'))
    for i in range(q):
        s, t = list(map(int, input().rstrip('\n').split()))
        if wl[s-1][t-1] == INF:
            print(-1)
        else:
            print(wl[s-1][t-1] - 1)


if __name__ == '__main__':
    slove()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9
minnum = 0
for i in range(n):
  minnum += abs(a[i]-(left+(i+1)))

ans = 0
def cal(num):
  global minnum
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    ans = mid
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))

### FIXED CODE ###

from functools import lru_cache
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))