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

import numpy as np
N = int(input())
S = input()

l_r = [i for i, s in enumerate(S) if s=='R']
l_g = [i for i, s in enumerate(S) if s=='G']
l_b = [i for i, s in enumerate(S) if s=='B']

ans = len(l_r)*len(l_g)*len(l_b)

for dis in range(1, N//2+1):
  for i in range(1, N-2*dis+1):
    j = i+dis
    k = j+dis
    if len(set([S[i-1], S[j-1], S[k-1]]))==3:
      ans -= 1
      
print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
S = input()

l_r = set()
l_g = set()
l_b = set()
for i in range(N):
  if S[i]=='R':
    l_r.add(i)
  if S[i]=='G':
    l_g.add(i)
  if S[i]=='B':
    l_b.add(i)

ans = len(l_r)*len(l_g)*len(l_b)

for r in l_r:
  for g in l_g:
    mi = min(r, g)
    ma = max(r, g)
    l = ma - mi
    if ma+l in l_b:
      ans -= 1
    if mi-l in l_b:
      ans -= 1
    if l%2==0 and l//2 + mi in l_b:
      ans -= 1

print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())


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


ans = []
for x in range(len(A)):
    for y in range(x+1, len(A)):
        ans.append(A[x]*A[y])
ans.sort()
print(ans[K-1])



### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())

A = np.array(list(map(int, input().split())))
A.sort()

pos = A[A > 0]
neg = A[A < 0]
zero = A[A == 0]

l = -10**18
r = 10**18

while l + 1 < r:
    x = (l+r) // 2
    cnt = 0
    if x >= 0:
        cnt += N * len(zero)

    cnt += A.searchsorted(x//pos, side="right").sum()
    cnt += (N - A.searchsorted(-(-x//neg), side="left")).sum()
    cnt -= np.count_nonzero(A * A <= x)
    cnt //= 2

    if cnt >= K:
        r = x
    else:
        l = x

print(r)
### BUGGY CODE ###

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 a in range(1 , K+1):
    for b in range(1 ,K+1):
        for c in range(1 , K+1):
            ans = ans + gcd(a,b,c)
        
print(ans)

### FIXED CODE ###

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 a in range(1 , K+1):
    for b in range(1 ,K+1):
        for c in range(1 , K+1):
            ans = ans + gcd(a,b,c)
       """
for a in range(1,K + 1):
    for b in range(1, K + 1):
        ab = math.gcd(a , b)
        for c in range(1, K+1):
            ans += math.gcd(ab , c)
        
print(ans)
### BUGGY CODE ###

import collections
import math
s = input()
n = len(s)
cnt = 0
lista = []
for i in range(n):
    inta = int(s[-i - 1:n])
    lista.append(inta)
listb = []
for i in range(n):
    intb = lista[i] % 2019
    listb.append(intb)
c = collections.Counter(listb)
for i in listb:
    if i == 0:
        cnt += 1
for i in c.most_common():
    match = i[1]
    if match >= 2:
        cnt += match * (match - 1) // 2
print(cnt)

### FIXED CODE ###

mod = [0]
pw = 1
for c in input()[::-1]:
    # 大きい数字での計算方法
    # a と z が互いに素のとき
    # x == y (mod z)なら
    # ax == ay (mod z)
    # 10000 == 1924 (mod 2019)
    # 100000 == 19240 (mod 2019)
    # 100000 == 1060 (mod 2019) 前のpwを10で掛けた分に2019を割る
    mod.append((int(c) * pw + mod[-1]) % 2019)
    pw = pw * 10 % 2019
from collections import *
# 8646 % 2019 = 余り570
# 282668646 % 2019 = 余り570
# 282668646 - 8646 = 282660000
# 282660000 % 2019 = 140000 余り0
# 余りが同じものをn(n - 1) / 2する
print(sum(v * (v - 1) // 2 for v in Counter(mod).values()))
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
count = 0
for i in range(N):
    for n in range(i + 1):
        if P[n] < P[i]:
            break
        if i == n:
            count += 1
print(count)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
MIN = list()
count = 0
MIN.append(P[0])
for i in range(1, N):
    MIN.append(min(MIN[i - 1], P[i]))
for i in range(0, N):
    if P[i] <= MIN[i]:
        count += 1
print(count)
### BUGGY CODE ###

def DP_B() :
    N, K = map(int, input().split())
    h = [int(x) for x in input().split()]
    dp = [10**10]*N

    dp[0] = 0
    for i in range(1,N) :
        for k in range(1,K+1) :
            if i >= k :
                dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))

    return dp[N-1]

print(DP_B())


### FIXED CODE ###

def DP_B() :
    N, K = map(int, input().split())
    h = [int(x) for x in input().split()]
    dp = [10**10]*N

    dp[0] = 0
    for i in range(1,N) :
        for k in range(1,K+1) :
            if i >= k :
                dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))

    return dp[N-1]

print(DP_B())
### BUGGY CODE ###

import copy

s = input().split()

n = int(s[0])
m = int(s[1])


ll = [set() for j in range(n + 1)]
sl = set()

s1 = {1}
s2 = set()


for i in range(m):
    t = input().split()
    sl.add(int(t[0]))
    sl.add(int(t[1]))
    ll[int(t[0])].add(int(t[1]))
    ll[int(t[1])].add(int(t[0]))


if sum(sl) < int(((n + 1) * n ) / 2):
    print("No")
    #print(sl,int(((n + 1) * n ) / 2))
else:
    count = 0
    goal = [0 for i in range(n)]
    out = 0

    while 1:
        s2.clear()
        out += 1
        for i in range(1,n+1):
            if len(s1 & ll[i]) != 0:
                s3 = list(s1 & ll[i])
                #print(s3)
                goal[i-1] = s3[0]
                s2.add(i)
                count += 1
                ll[i].clear()
        s1 = copy.deepcopy(s2)
        #print(s1,s2)

        if out >= 2000 or count >= n:
            break
    print("Yes")
    for i in range(1,n):
        print(goal[i])

    #print(count,out)
    #print(goal)


### FIXED CODE ###

import collections

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

coriddorList = [set() for i in range(n+1)]
deepList = [-1 for i in range(n+1)]


for i in range(m):
    a,b = list(map(int,input().split()))
    coriddorList[a].add(b)
    coriddorList[b].add(a)

checkList = [0] * (n + 1)
ansList = [0] * (n + 1)
checkList[1] = 1
q = collections.deque()
q.appendleft(1)

while len(q) > 0:
    value = q.pop()
    for k in coriddorList[value]:
        if checkList[k] == 0:
            checkList[k] = 1
            ansList[k] = value
            q.appendleft(k)

print("Yes")
for i in range(2,n+1):
    print(ansList[i])
### BUGGY CODE ###

A,B,K = map(int, input().split())
for _ in range(K):
    if A>0:
        A -= 1
    elif B>0:
        B -= 1
print(A,B)


### FIXED CODE ###

A,B,K = map(int, input().split())
if A>K:
    print(A-K,B)
elif A+B>K:
    print(0,A+B-K)
else:
    print(0,0)
### BUGGY CODE ###

def factorial(n, mod=10**9+7):
    a = 1
    for i in range(1,n+1):
        a = a * i % mod
    return a


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod=10**9+7):
    if n < k or k < 0:
        result = 0
    else:
        a = factorial(n, mod=mod)
        b = factorial(k, mod=mod)
        c = factorial(n-k, mod=mod)
        result = (a * power(b, mod-2, mod=mod) * power(c, mod-2, mod=mod)) % mod
    return result

n, k = map(int, input().split())
MOD = 10**9 + 7

if k >= n:
  print(comb(2*n-1, n))
  quit()

def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


fl = [-1]*(k+1)
fl[0] = 1
def f(i):
  global fl
  if fl[i] > 0: return fl[i]
  else:
    res = f(i-1)*(n-i+1)*(n-i)
    t = power(i, MOD-2)
    res *= t
    res %= MOD
    res *= t
    res %= MOD
    fl[i] = res
    return res


ans = 0
for i in range(k+1):
  ans += f(i)
  ans %= MOD


print(ans % MOD)

### FIXED CODE ###

def factorial(n, mod=10**9+7):
    a = 1
    for i in range(1,n+1):
        a = a * i % mod
    return a


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


def comb(n, k, mod=10**9+7):
    if n < k or k < 0:
        result = 0
    else:
        a = factorial(n, mod=mod)
        b = factorial(k, mod=mod)
        c = factorial(n-k, mod=mod)
        result = (a * power(b, mod-2, mod=mod) * power(c, mod-2, mod=mod)) % mod
    return result

n, k = map(int, input().split())
MOD = 10**9 + 7

if k >= n:
  print(comb(2*n-1, n))
  quit()

def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


fl = [-1]*(k+1)
fl[0] = 1
def f(i):
  global fl
  if fl[i] > 0: return fl[i]
  else:
    if i <= n//2:
      res = f(i-1)*(n-i+1)*(n-i)
      t = power(i, MOD-2)
      res *= t
      res %= MOD
      res *= t
      res %= MOD
      fl[i] = res
      return res
    else:
      res = f(n-i) * (n-i)
      res *= power(i, MOD-2)
      res %= MOD
      fl[i] = res
      return res


if k <= n//2:
  fl = [-1]*(k+1)
  fl[0] = 1
  def f(i):
    global fl
    if fl[i] > 0: return fl[i]
    else:
      res = f(i-1)*(n-i+1)*(n-i)
      t = power(i, MOD-2)
      res *= t
      res %= MOD
      res *= t
      res %= MOD
      fl[i] = res
      return res

  ans = 0
  for i in range(k+1):
    ans += f(i)
    ans %= MOD
else:
  fl = [-1]*(n+1)
  fl[0] = comb(n, k) * comb(n-1, k) % MOD
  def f(i):
    global fl
    if fl[i-k] > 0: return fl[i-k]
    else:
      res = f(i-1)*(n-i+1)*(n-i)
      t = power(i, MOD-2)
      res *= t
      res %= MOD
      res *= t
      res %= MOD
      fl[i-k] = res
      return res
  
  ans = 0
  for i in range(k+1, n+1):
    ans += f(i)
    ans %= MOD
  ans = comb(2*n-1, n) - ans
  ans %= MOD


print(ans % MOD)
### BUGGY CODE ###

def main():
    h, n = map(int, input().split())
    magic_list = []

    for _ in range(n):
        a, b = map(int, input().split())
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    inf = 1 << 40
    max_attack = max(magic_list)[0]
    dp = [inf] * (h + max_attack)
    dp[0] = 0

    # time O(HN)
    for hp in range(1, h + max_attack):
        for attack, mp in magic_list:
            if hp >= attack and dp[hp - attack] < inf:
                dp[hp] = min(dp[hp], dp[hp - attack] + mp)

    return min(dp[h:])


main()


### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    magic_list = []

    for _ in range(n):
        a, b = map(int, input().split())
        magic_list.append((a, b))

    ans = solve(h, magic_list)
    print(ans)


def solve(h, magic_list):
    # 1-origin
    inf = 1 << 40
    max_attack = max(magic_list)[0]
    dp = [inf] * (h + max_attack)
    dp[0] = 0

    # time O(HN)
    for hp in range(1, h + max_attack):
        for attack, mp in magic_list:
            if hp >= attack and dp[hp - attack] < inf:
                dp[hp] = min(dp[hp], dp[hp - attack] + mp)

    return min(dp[h:])


main()
### BUGGY CODE ###

mod = 998244353
N, S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0 for i in range(S+1)] for j in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] * 2
        if j + A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
        dp[i+1][j] %= mod

print(dp[N][S])


### FIXED CODE ###

mod = 998244353
N, S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0 for i in range(S+1)] for j in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += dp[i][j] * 2
        if j + A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j]
        dp[i+1][j] %= mod

print(dp[N][S])
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [ int(input()) for i in range(q) ]
a_count = a.count

for i in range(1,n+1):
    x = a_count(i)
    if k-q+x > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
a = [ int(input()) for i in range(q) ]
score = [k-q]*n
for i in a:
    score[i-1] += 1
for i in score:
    print('Yes' if i > 0 else 'No')
### BUGGY CODE ###

N = int(input())

l = list(map(int, input().split()))

count = 0

for i in range(N):
    m = l[:i+1]
    if min(m) == l[i]:
        count += 1

print(count)


### FIXED CODE ###

N = int(input())

l = list(map(int, input().split()))

count = 0
s = l[0]
for i in range(N):
    if l[i] <= s:
        count += 1
        s = l[i]


print(count)
### BUGGY CODE ###

n,k = map(int,input().split())
m = n
while m > k/2:
  m = abs(n-k)
  if n == m:
    break
print(m)

### FIXED CODE ###

n,k = map(int,input().split())
m = n
m = m%k
if m > int(k/2):
  ans = abs(m-k)
else:
  ans = m
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

count = 0

for i in range(n-3):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        else:
            for k in range(j+1, n):
                if j - i == k - j:
                    continue
                else:
                    if s[i] == s[k] or s[j] == s[k]:
                        continue
                    else:
                        count += 1

print(count)


### FIXED CODE ###

n = int(input())
s = input()

nr = s.count("R")
ng = s.count("G")
nb = s.count("B")

count = nr * ng * nb

for i in range(n-2):
    for j in range(i+1, (n+i+1)//2):
        if s[i] == s[j]:continue
        else:
            k = 2*j - i # k - j = j - i
            if s[i] == s[k]:continue
            if s[j] == s[k]:continue
            count -= 1

print(count)
### BUGGY CODE ###

K, S = map(int, input().split())

ans = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            ans += ((x + y + z) == S)
print(ans)   


### FIXED CODE ###

K, S = map(int, input().split())

ans = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        ans += ((0<=z<=K))
print(ans)
### BUGGY CODE ###

a, b, x = input().split()
a = int(a)
b = int(b)
x = int(x)
count = 0
for i in range(a,b+1):
      if i%x == 0:
            count = count + 1
      else:
            count = count
print(count)


### FIXED CODE ###

a, b, x = map(int, input().split())
c = b//x
d = (a-1)//x
print(c - d)
### BUGGY CODE ###

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

b = []

b.append(a[0])
for i in range(1, n):
    if(i%2 == 1):
        b.append(a[i])  
    else:
        b.insert(0, a[i])
   

if(n % 2 == 0):
    b.reverse()
    

print(*b)


### FIXED CODE ###

from collections import *
n = int(input())
a = [int(i) for i in input().split()]

b = deque()

b.append(a[0])
for i in range(1, n):
    if(i%2 == 1):
        b.append(a[i])  
    else:
        b.appendleft(a[i])
   

if(n % 2 == 0):
    b.reverse()
    

print(' '.join(map(str, b)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""

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

lr = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
lrac = [[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    ac = 0
    for j in range(n+1):
        ac += lr[i][j]
        lrac[i][j] = ac

for _ in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = 0
    for i in range(pi, qi+1):
        ans += lrac[i][qi] - lrac[i][pi-1]
    
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""

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

lr = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
    
for i in range(n+1):
    for j in range(n):
        lr[i][j+1] += lr[i][j]
for i in range(n+1):
    for j in range(n):
        lr[j+1][i] += lr[j][i]

for _ in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = lr[qi][qi] - lr[qi][pi-1] - lr[pi-1][qi] +lr[pi-1][pi-1]
    
    print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
r = 0
ans = s
for i in range(q):
    d = input().split()
    if len(d)==1:
        r += 1
    else:
        f = int(d[1])
        c = d[2]
        if (f+r)%2 == 1:
            ans = c + ans
        else:
            ans = ans + c

if r%2:
    ans = ans[::-1]
print(ans)

### FIXED CODE ###

ans = input()
q = int(input())
r = 0
p = ""
for i in range(q):
    d = input().split()
    if len(d)==1:
        r += 1
    else:
        f = int(d[1])
        c = d[2]
        if (f+r)%2 == 1:
            p += c
        else:
            ans += c
ans = p[::-1] + ans
if r%2:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

N, K, *LR = [int(_) for _ in open(0).read().split()]
L = LR[::2]
R = LR[1::2]
mod = 998244353
dp = [0] * 3 * N
dp[1] = 1
for s in range(1, N):
    for l, r in zip(L, R):
        for d in range(l, r + 1):
            dp[s + d] += dp[s]
            dp[s + d] %= mod
print(dp[N])


### FIXED CODE ###

N, K = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(K)]
mod = 998244353


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


st = SegmentTree([0] + [1] + [0] * N, lambda x, y: x + y, 0)
for i in range(2, N + 1):
    v = 0
    for l, r in LR:
        il = max(0, i - r)
        ir = max(0, i - l + 1)
        v += st.query(il, ir)
        v %= mod
    st.update(i, v)
ans = st.query(N, N + 1)
print(ans)
### BUGGY CODE ###

N = int(input())

A = [int(input()) for _ in range(N)]

B = sorted(A)

ans = 0
skip_flag = False
for i in range(N):
    if skip_flag == False:
        idx = A.index(B[i])
        if abs(i - idx) % 2 == 0: # あまり０なら操作２だけで所定の位置に動かせる
            continue
        else:
            ans += 1
            # 次のやつも同時にできるか
            if i < N-1:
                next_idx = A.index(B[i+1])
                if abs(i+1 - next_idx) % 2 == 1:
                    skip_flag = True
    else:
        skip_flag = False
        continue

print(ans)


### FIXED CODE ###

import math

N = int(input())

A = [int(input()) for _ in range(N)]

idx_A = {}
for i in range(N):
    idx_A[A[i]] = i

B = tuple(sorted(A))

"""
ソート後の位置までの距離が奇数だと操作１が一回必要になる
一度の操作１で最大で２個までのソート後の位置までの距離が奇数のものを偶数にずらしてあげられる
ので、正しい位置までの距離が奇数のものの個数をしらべて、最小の操作１の回数を求める
"""
cnt = 0
for i in range(N):
    if abs(i - idx_A[B[i]]) % 2 == 0: # あまり０なら操作２だけで所定の位置に動かせる
        continue
    else:
        cnt += 1


print(math.ceil(cnt/2))
### BUGGY CODE ###

import math
import numpy as np

H,N=map(int,input().split())
A_list=[]
B_list=[]
for i in range(N):
    A,B=map(int,input().split())
    A_list.append(A)
    B_list.append(B)

amax=max(A_list)

inf=float('inf')
dp=np.array([0]+[inf]*(H+amax))

for i in range(N):
    A=A_list[i]
    B=B_list[i]
    for j in range(A,1+H+amax):
        if dp[j-A]+B < dp[j]:
            dp[j]=dp[j-A]+B

    #if A > H and B < dp[-1]:
    #    dp[-1]=B
    #else:
    #    for j in range(A,1+H):
    #        if dp[j-A]+B<dp[j]:
    #            dp[j]=dp[j-A]+B
    
    #    minA=np.amin(dp[H-A:])+B
    #    if minA < dp[-1]:
    #        dp[-1]=minA

print(int(np.amin(dp[H:])))


### FIXED CODE ###

import math

def main():
    H,N=map(int,input().split())

    inf=float('inf')
    dp=[0]+[inf]*H

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            #dp[-1]=min(B,dp[-1])
            if B < dp[-1]:
                dp[-1]=B
        else:
            for j in range(A,H+1):
                #dp[j]=min(dp[j-A]+B,dp[j])
                if dp[j-A]+B<dp[j]:
                    dp[j]=dp[j-A]+B

                if j > H-A:
                    #dp[-1]=min(dp[-1],dp[j]+B)
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print(dp[-1])

main()
### BUGGY CODE ###

n=int(input())
a = list(map(int, input().split()))
q=int(input())
bc=[]
for i in range(q):
    bc.append(list(map(int, input().split())))


for gyou in range(q):
    a = [bc[gyou][1] if i==bc[gyou][0] else i for i in a]
    print(sum(a))

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
bc=[]
for i in range(q):
    bc.append([int(x) for x in input().split()])

a_cnt=[0]*(10**5+1)

for i in range(len(a)):
	a_cnt[a[i]]+=1

a_goukei=sum(a)

for gyou in range(q):
	a_goukei+=(bc[gyou][1]-bc[gyou][0])*a_cnt[bc[gyou][0]]
	print(a_goukei)
	a_cnt[bc[gyou][1]]+=a_cnt[bc[gyou][0]]
	a_cnt[bc[gyou][0]]=0
### BUGGY CODE ###

import math

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

L = sorted(L,reverse=True)


while M > 0:
	L[0] = int(math.floor(L[0] / 2))
	L = sorted(L,reverse=True)
	
	M -= 1
	
print(sum(L))



### FIXED CODE ###

import heapq

N,M = map(int, input().split())
L = [-int(i) for i in input().split()]
heapq.heapify(L)



for i in range(M):
    h = -(-heapq.heappop(L) // 2)
 
    heapq.heappush(L,h)

print(-sum(L))
### BUGGY CODE ###

import math
ans=0
i = int(input())
for a in range(1,i+1):
  for b in range(1,i+1):
    for c in range(1,i+1):
      n=math.gcd(math.gcd(a,b),c)
      ans+=n
print(ans)
      

### FIXED CODE ###

from math import gcd
ans=0
i = int(input())
for a in range(1,i+1):
  for b in range(1,i+1):
    for c in range(1,i+1):
      n=gcd(gcd(a,b),c)
      ans+=n
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
def quick_sort(a):
    if len(a)<= 1:
        return a
    else:
        b=[]
        c=[]
        for i in range(1, len(a)):
            if a[i]<a[0]:
                b.append(a[i])
            else:
                c.append(a[i])
        return quick_sort(b)+[a[0]]+quick_sort(c)
def abs(x):
    if x>=0:
        return x
    else:
        return x*(-1)
B=[0]*N
for j in range(N):
    B[j]=A[j]-j-1
bh=quick_sort(B)[0]
bt=quick_sort(B)[N-1]
def sad(A,b):
  s=[0]*(len(A))
  for m in range(len(A)):
    s[m]=abs(A[m]-(b+m+1))
  return s
def sum(A):
  sum=0
  for n in range(len(A)):
    sum=sum+A[n]
  return sum
l=[]
for o in range(bh-5,bt+5):
  l.append(sum(sad(A,o)))
print(quick_sort(l)[0])

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
  B.append(A[i]-i-1)
B.sort()
if N%2==0:
  b=(B[N//2]+B[N//2-1])//2
else:
  b=B[N//2]
sad=0
for j in range(N):
  sad=sad+abs(B[j]-b)
print(sad)