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

import bisect

N, M, Q = map(int, input().split())

trains = [list(map(int, input().split())) for i in range(M)]
intervals = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])
L = [train[0] for train in trains]
R = [train[1] for train in trains]
for i in range(Q):
    pi, qi = intervals[i]
    right = bisect.bisect_right(R, qi)
    A = sorted(L[:right])
    left = bisect.bisect_left(A, pi)
    print(right - left)


### FIXED CODE ###

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])
### BUGGY CODE ###

import bisect
import sys


def make_primes(n):
    primes = [2]
    for i in range(3, n, 2):
        if is_prime(i, primes):
            primes.append(i)
    return primes


def is_prime(n, primes):
    for prime in primes:
        if n % prime == 0:
            return False
        if n // 2 < prime:
            break
    return True


def make_like2017():
    like2017 = [0]
    for idx in range(1, len(primes)):
        if is_prime((primes[idx] + 1) // 2, primes):
            like2017.append(like2017[idx - 1] + 1)
        else:
            like2017.append(like2017[idx - 1])
    return like2017


def sol(l, r):
    if l == r:
        if is_prime(l, primes) and is_prime((l + 1) // 2, primes):
            return 1
        else:
            return 0

    idx_l = bisect.bisect_left(primes, l)
    idx_r = bisect.bisect_left(primes, r)

    if idx_l == idx_r:
        return 0
    else:
        idx_l = max(0, idx_l - 1)
        idx_r = min(len(like2017s) - 1, idx_r)
        return like2017s[idx_r] - like2017s[idx_l]


N_MAX = 10 ** 5 + 1

Q = int(sys.stdin.readline())
primes = make_primes(N_MAX)
like2017s = make_like2017()

for _ in range(Q):
    l, r = map(int, sys.stdin.readline().split())
    print(sol(l, r))


### FIXED CODE ###

import math
import bisect
  
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

def get_like_2017(N):
  nums = set([i for i in range(2,N+1)])
  for i in range(2, int(math.sqrt(N))+1):
    for j in range(2,int(N//i)+1):
      if i*j in nums: nums.remove(i*j)
  
  nums_like_2017 = set([])
  for num in nums:
    if is_prime(int((num+1)/2)) is True:  nums_like_2017.add(num)
  return nums_like_2017

nums_like_2017 = sorted(list(get_like_2017(10**5)))

Q = int(input())
for _ in range(Q):
  l,r = map(int, input().split())
  idx_l = bisect.bisect_left(nums_like_2017, l)
  idx_r = bisect.bisect_right(nums_like_2017, r)
 
  print(idx_r-idx_l)
### BUGGY CODE ###

from collections import deque
import sys

class Tree:
    def __init__(self, n, init_list, root=1):
        self.num = (n + 1)
        self.parents = [-1] * self.num
        self.first_child = [-1] * self.num
        self.next_child = [-1] * self.num
        self.check = [-1] * self.num
        self.g = {i: [] for i in range(1, self.num)}
        self.make_g(init_list, root)

    def make_g(self, con, root):
        m = len(con)
        for i in range(m):
            self.g[con[i][0]].append(con[i][1])
            self.g[con[i][1]].append(con[i][0])
        q = deque([root])
        while q != deque():
            node = q.pop()
            self.check[node] = 1
            cnt = 0
            for i, sub_node in enumerate(self.g[node]):
                if self.check[sub_node] != -1:
                    continue
                if cnt == 0:
                    self.first_child[node] = sub_node
                self.parents[sub_node] = node
                if i != len(self.g[node])-1:
                    self.next_child[sub_node] = self.g[node][i+1]
                q.append(sub_node)
                cnt += 1

    def childs(self, node):
        child_list = []
        if self.first_child[node] != -1:
            child_list.append(self.first_child[node])
            node = self.first_child[node]
            while 1:
                if self.next_child[node] == -1:
                    break
                else:
                    child_list.append(self.next_child[node])
                node = self.next_child[node]
        return child_list

    def parent(self, n):
        return self.parents[n]

input = sys.stdin.readline
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N-1)]
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

tr = Tree(N, AB)

q = deque()
q.extend(tr.childs(1))
while q != deque():
    node = q.pop()
    V[node] += V[tr.parent(node)]
    if tr.childs(node):
        q.extend(tr.childs(node))

print(*V[1:])


### FIXED CODE ###

from collections import deque

N, Q = map(int, input().split())
AB = {i: set() for i in range(1, N+1)}
for i in range(N - 1):
    tmpA, tmpB = map(int, input().split())
    AB[tmpA].add(tmpB)
    AB[tmpB].add(tmpA)
P = [0] * Q
X = [0] * Q
V = [0] * (N + 1)
for i in range(Q):
    P, X = map(int, input().split())
    V[P] += X

check = [0]*(N + 1)
q = deque()
q.append(1)
check[1] = 1
while q != deque():
    node = q.pop()
    for i in AB[node]:
        if check[i] == 1:
            continue
        V[i] += V[node]
        check[i] = 1
        q.appendleft(i)
print(*V[1:])
### BUGGY CODE ###

def gcdf(x,y):
  if y==0:return x
  if y>x:return gcdf(y,x)
  else:return gcdf(y,x%y)

N=int(input())
A=[int(s)for s in input().split()]
gmax=0
for i in range(N):
  gcd=A[0] if i!=0 else A[1]
  for j in range(N):
    if i==j:continue
    if gcd==1:break
    gcd=gcdf(gcd,A[j])
  gmax=max((gmax,gcd))
print(gmax)
    

### FIXED CODE ###

def gcdf(x,y):
  if y==0:return x
  if y>x:return gcdf(y,x)
  else:return gcdf(y,x%y)

N=int(input())
A=[int(s)for s in input().split()]
A=sorted(A)
if N==2:
  print(A[1])
  exit()
r=[]
for i in range(1,N):
  r.append(gcdf(A[i],A[0]))
r=sorted(r)
gcd=r[1]
for i in range(2,N-1):
  gcd=gcdf(r[i],gcd)
  
gcd2=A[1]
for i in range(2,N):
  gcd2=gcdf(A[i],gcd2)
print(max((gcd,gcd2)))
### BUGGY CODE ###

N,K,*A = map(int,open(0).read().split())

for k in range(K):
    if all(A) == N:
        break
    B = [0] * N
    for n in range(N):
        L = max(0, n-A[n])
        R = min(N-1 , n + A[n])
        B[L] += 1
        if R+1 != N:
            B[R+1] -= 1
    
    ruiseki = [0] * N
    ruiseki[0] = B[0]
    for i in range(1,N):
        ruiseki[i] = ruiseki[i-1] + B[i]
        
    A = ruiseki[:]
print(*ruiseki,sep=" ")    
   


### FIXED CODE ###

from itertools import accumulate
#from operator import add

N,K = map(int,input().split())
A = map(int,input().split()) 
for k in range(K):
    B = [0] * N
    for i,x in enumerate(A):
        L = max(0, i-x)
        R = min(N-1, i+x)
        B[L] += 1
        if R+1 != N:
            B[R+1] -= 1
    #L = accumulate(B,add) 
    L = list(accumulate(B))[:]
    if L == A:
        break
    A = L
print(*A)
### BUGGY CODE ###

import queue
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
for i in range(q):
    children = queue.Queue()
    p, x = map(int, input().split())
    children.put(p - 1)
    while not children.empty():
        c = children.get()
        counter[c] += x
        for j in tree[c]:
            children.put(j)
print(*counter)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[] for i in range(n)]
counter = [0] * n
visited = [False] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    # tree[b - 1].append(a - 1)
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
queue = deque([0])
visited[0] = True
while queue:
    now = queue.pop()
    for j in tree[now]:
        if visited[j]:
            continue
        counter[j] += counter[now]
        visited[j] = True
        queue.append(j)
print(*counter)
### BUGGY CODE ###

A, B, C, D = map(int, input().split())
ans = 0
for i in range(A, B+1):
  if i%C!=0 and i%D!=0:
    ans += 1
print(ans)

### FIXED CODE ###

from fractions import gcd
A, B, C, D = map(int, input().split())
E = C*D//gcd(C, D)
X = B - B//C - B//D + B//E
Y = A-1 - (A-1)//C - (A-1)//D + (A-1)//E
print(X-Y)
### BUGGY CODE ###

k, K = 80, 1 << 80
nu = lambda L: int("".join([bin(a)[2:].zfill(k) for a in L[::-1]]), 2)
st = lambda n: bin(n)[2:].zfill((len(A)+len(B)-1)*k) + "_"
li = lambda s: [int(a, 2) % 998244353 for a in [s[-(i+1)*k-1:-i*k-1] for i in range(len(A)+len(B)-1)]]
input()
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*li(st(nu(A) * nu(B))))

### FIXED CODE ###

def convolve(a, b):
    def fft(f):
        d = n // 2
        v = w
        while d >= 1:
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, u * (f[j] - f[j+d]) % p
                u = u * v % p
            v = v * v % p
            d //= 2
 
    def ifft(f):
        d = 1
        while d < n:
            v = pow(invw, n // (2 * d), p)
            u = 1
            for i in range(d):
                for j in range(i, n, 2*d):
                    f[j+d] *= u
                    f[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % p
                u = u * v % p
            d *= 2
 
    p, g = 998244353, 3
    n0, n1 = len(a), len(b)
    n = 1 << (max(n0, n1) - 1).bit_length() + 1
    a = a + [0] * (n-n0)
    b = b + [0] * (n-n1)
    w = pow(g, (p - 1) // n, p)
    invw = pow(w, p-2, p)
    fft(a), fft(b)
    for i in range(n):
        a[i] = a[i] * b[i] % p
    ifft(a)
    invn = pow(n, p - 2, p)
    return [a[i] * invn % p for i in range(n0 + n1 - 1)]

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
print(*convolve(A, B))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    S = reversed(list(input().rstrip()))
    counter = defaultdict(int)
    mod = 2019
    counter[0] += 1
    num = 0
    for i, c in enumerate(S):
        num += int(c) * 10**(i)
        counter[num%mod] += 1
    ans = 0
    for v in counter.values():
        ans += (v * (v-1)) // 2
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    S = input().rstrip()
    counter = defaultdict(int)
    mod = 2019
    counter[0] += 1
    num = 0
    d = 1
    for c in S[::-1]:
        num += int(c) * d
        num %= mod
        counter[num] += 1
        d *= 10
        d %= mod
    ans = 0
    for v in counter.values():
        ans += (v * (v-1)) // 2
    print(ans)

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

from collections import defaultdict
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)

def dfs(v, o):
    if memo[v]:
        return memo[v]

    if len(parents[v]) > 1:
        memo[v] = []
        return []
    for c in G[v]:
        parents[c].add(v)

    ancestors.add(v)
    for c in G[v]:
        if c in ancestors - {o}:
            ancestors.remove(v)
            memo[v] = []
            return []

    ret = []
    if any(c == o for c in G[v]):
        ret = [v]
    else:
        for c in G[v]:
            ret = dfs(c, o)
            if ret:
                ret.append(v)
                break

    ancestors.remove(v)
    for c in G[v]:
        parents[c].remove(v)
    memo[v] = ret
    return ret

for v in range(1, N+1):
    ancestors = set()
    parents = defaultdict(set)
    memo = [None] * (N+1)
    cand = dfs(v, v)
    if cand:
        print(len(cand))
        print(*cand, sep='\n')
        break
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
    A, B = map(int, input().split())
    G[A].append(B)

def dfs(v, o):
    for c in G[v]:
        if c == o:
            return [v]
    for c in G[v]:
        if visited[c]:
            continue
        visited[c] = True
        ret = dfs(c, o)
        if ret:
            return [v] + ret

for v in range(1, N+1):
    visited = [False] * (N+1)
    cur = dfs(v, v)
    if cur:
        break
else:
    print(-1)
    exit()

while True:
    cur_set = set(cur)
    unused = None
    for i in range(len(cur)):
        u, v = cur[i], cur[(i+1) % len(cur)]
        for c in G[u]:
            if c == v:
                continue
            elif c in cur_set:
                unused = (i, cur.index(c))
                break

    if not unused:
        break
    else:
        t, s = unused
        nxt = []
        i = s
        while i != t:
            nxt.append(cur[i])
            i = (i + 1) % len(cur)
        nxt.append(cur[t])
        cur = nxt

print(len(cur))
print(*cur, sep='\n')
### BUGGY CODE ###

N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
cnt = 0
for a in A:
    for b in B:
        if a >= b:
            continue
        cnt += sum(b < c for c in C)
print(cnt)


### FIXED CODE ###

import bisect
N = int(input())
A = sorted(map(int, input().split()))
B = map(int, input().split())
C = sorted(map(int, input().split()))
print(sum(bisect.bisect_left(A, b) * (N - bisect.bisect(C, b)) for b in B))
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    l = len(format(max(a),'b'))
    a = [format(a[i],'0{}b'.format(l)) for i in range(n)]
    ans = [[] for i in range(n)]
    for i in range(l):
        s = 0
        for j in range(n):
            s+=int(a[j][i])
        if s%2!=0:
            for j in range(n):
                ans[j].append(str((int(a[j][i])+1)%2))
        else:
            for j in range(n):
                ans[j].append(a[j][i])
    for i in range(n):
        ans[i] = ''.join(ans[i])
        ans[i] = str(int(ans[i],2))
    print(' '.join(ans))

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    b = a[0] ^ a[1]
    for i in range(2,n):
        b = b ^ a[i]
    ans = []
    for i in range(n):
        ans.append(b ^ a[i])
    ans = list(map(str,ans))
    print(' '.join(ans))

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

def possibleCombos(num):
    num2 = num - 1
    return (num2*num2 + num2)//2
N = int(input())
A = [i for i in input().split()]
keys = {i:A.count(i) for i in sorted(set(A)) }
for i in A:
    result = 0
    for k in keys.keys():
        count = keys[k] - 1 if k == i else keys[k]
        result += possibleCombos(count)
    print(result)

### FIXED CODE ###

def possibleCombos(num):
    num2 = num - 1
    return (num2*num2 + num2)//2
N = int(input())
A = [int(i) for i in input().split()]
data = [0] * (N+1)
total = 0
for i in A:

    data[i] +=1

for i in data:
    total += possibleCombos(i)
for i in A:
    result = total - possibleCombos(data[i]) + possibleCombos(data[i]-1)
    print(result)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

L = str(input())
L_list = [0 for i in range(len(L))]
for i in range(len(L)):
    L_list[i] = int(L[i])
n = len(L)
num = 0
L_list.reverse()
for i in range(n):
    num += L_list[i]*2**i


def count2digit(num):
    cnt = 0
    while num > 0:
        if num % 2 == 1:
            cnt +=1
        num //= 2
    return cnt

ans = 1 # (0,0)
for i in range(1,num+1):
    ans += 2**count2digit(i) % mod
    ans = ans % mod

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

L = str(input())
n = len(L)
dp = [[0,0] for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if L[i] == "0": #a+b = 0
        dp[i+1][0] = dp[i][0]
        dp[i+1][1] = dp[i][1]
    else:
        dp[i+1][1] = (dp[i][0] + dp[i][1]) % mod

    if L[i] == "0":
        dp[i+1][1] = (dp[i+1][1] + dp[i][1]*2) % mod
    else:
        dp[i+1][0] = (dp[i+1][0] + dp[i][0]*2) % mod
        dp[i+1][1] = (dp[i+1][1] + dp[i][1]*2) % mod


print(sum(dp[n]) % mod)
### BUGGY CODE ###

import collections
N, M = map(int, input().split())
A = [0]*M
B = [0]*M
for i in range(M):
  A[i],B[i] = map(int,input().split())
ans = 0
f = [-1]*N
for i in range(M):

  if f[A[i]-1] == -1 and f[B[i]-1] == -1:
    f[A[i]-1] = i
    f[B[i]-1] = i
  elif f[A[i]-1] != -1 and f[B[i]-1] == -1:
    f[B[i]-1] = f[A[i]-1]
  elif f[A[i]-1] == -1 and f[B[i]-1] != -1:
    f[A[i]-1] = f[B[i]-1]
  else:
    f = [f[B[i]-1] if j == f[A[i]-1] else j for j in f]
ff = [i for i in f if i != -1]
if ff != []:
  print(max(collections.Counter(ff).values()))
else:
  print(1)

### FIXED CODE ###

# cf. 16315733
N, M = list(map(int, input().split()))
# upperは、根なら-その木の長さを、枝ならその木の根の要素のインデックスを指す。
upper = [-1] * N
# xの根を返す
def root(x):
  # xが根なら
  if upper[x] < 0:
    return x
  # xが枝なら
  else:
    # 根のインデックスをさかのぼる
    upper[x] = root(upper[x])
    # 根のインデックスを返す
    return upper[x]

# x,yが同じグループにあるかどうか判定する
def equiv(x, y):
  return root(x) == root(y)

def unite(x, y):
  x, y = root(x), root(y)
  if x != y:
    if upper[y] < upper[x]:
      #xとyの値をスワップ、必ずupper[y] >= upper[x]とするつまりxのほうが高い
      x,y = y,x
    # 要素の数を足す：結合後の要素の数を求める
    upper[x] += upper[y]
    # yの根をxにする（木が高い方を根にする）
    upper[y] = x
  return x == y

for i in range(M):
  a, b = list(map(int, input().split()))
  unite(a-1, b-1)
print(-min(upper))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort()
b.sort()
c.sort()
c = c[::-1]
answer,x,y = 0,0,0
for j in b:
	for k in range(x,n):
		if a[k] >= j:
			x = k
			break
		elif k == n-1:
			x = n
	for k2 in range(n):
		if c[k2] <= j:
			y = k2
			break
		elif k2 == n-1:
			y = n
	answer += x*y
print(answer)


### FIXED CODE ###

import bisect
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort()
c.sort()
answer = 0
for i in b:
	x = bisect.bisect_right(c,i)
	y = bisect.bisect_left(a,i)
	answer += (n-x)*y
print(answer)
### BUGGY CODE ###

N , M = map(int,input().split())
A =  map(int,input().split())
A = [a for a in A]

partial_sum_list = [0]
partial_sum = 0
res = 0
i = 0
while i < N:
    partial_sum += A[i]
    partial_sum_list.append(partial_sum)
    temp = partial_sum % M
    j = 0
    while j < len(partial_sum_list)-1:
        if temp == (partial_sum_list[j] % M):
            res += 1
        j += 1
    i = i + 1
print(res)

### FIXED CODE ###

N , M = map(int,input().split())
A =  map(int,input().split())
A = [a for a in A]

dic = {}
dic[0] = 0
partial_sum = 0
res = 0
i = 0
while i < N:
    partial_sum += A[i]
    a = partial_sum % M
    if a == 0:
        res += 1
    if a in dic:
        dic[a] += 1
        res += dic[a] - 1
    else:
        dic[a] = 1
        res += dic[a] - 1
    #res += dic[a]
    i = i + 1
print(res)
### BUGGY CODE ###

N = int(input())
A = []
A += list(map(int,input().split()))
S = 0
k = 0

Num = 0
Dum = 0
Gum = 0

for i in range(N-1):
    Num = i
    for j in range(Num+1):
        Dum += A[j]
    Gum += Dum * A[Num + 1]
    Dum = 0

print(Gum % 1000000007)


### FIXED CODE ###

N = int(input())
A = []
A += list(map(int,input().split()))
S = 0
k = 0

Dum = 0
Gum = 0

for i in range(0, N-1):
    Dum += A[i]
    Gum += Dum * A[i+1]

print(Gum % 1000000007)
### BUGGY CODE ###

x, n = map(int, input().split())
if n==0:
    print(x)
else:
    p = list(map(int, input().split()))
    p.sort()
    i = 0
    while i < n and p[i] < x:
        i += 1

    if p[i] != x:
        print(x)
    else:
        j = 1
        up = x+j
        down = x-j
        while True:
            if i-j>=0 and p[i-j] != x-j:
                print(x-j)
                break
            if i+j<n and p[i+j] != x+j:
                print(x+j)
                break
            j += 1


### FIXED CODE ###

x, n = map(int, input().split())
if n==0:
    print(x)
else:
    p = list(map(int, input().split()))
    p.sort()
    i = 0
    while i < n and p[i] < x:
        i += 1

    if p[i] != x:
        print(x)
    else:
        j = 1
        up = x+j
        down = x-j
        while True:
            if i-j>=0 and p[i-j] != x-j:
                print(x-j)
                break
            elif i-j < 0:
                print(x-j)
                break
            if i+j<n and p[i+j] != x+j:
                print(x+j)
                break
            elif i+j >= n:
                print(x+j)
                break
            j += 1
### BUGGY CODE ###

import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])

#　基本形
for i in range(1,N+1):
    dp[i][:wv[i-1][0]] = dp[i-1][:wv[i-1][0]]
    for j in range(wv[i-1][0],W+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-wv[i-1][0]]+wv[i-1][1])
print(int(dp[-1,-1]))

### FIXED CODE ###

import numpy as np

N,W = map(int,input().split())
wv = np.array([list(map(int,input().split())) for _ in range(N)])
dp=np.zeros([N+1,W+1])

#　繰り返し回数節約
for i in range(1,N+1):
    dp[i][:wv[i-1][0]] = dp[i-1][:wv[i-1][0]]
    dp[i][wv[i-1][0]:] = np.maximum(dp[i-1][wv[i-1][0]:],dp[i-1][:W+1-wv[i-1][0]]+wv[i-1][1])
print(int(dp[-1,-1]))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    b[i]=a[i]-(i+1)
s=0
for i in range(n):
    s+=b[i]
mean=s//(len(b))
ans=10**10
mi=mean-10**4
ma=mean+10**4
for i in range(mi,ma):
    w=0
    c=list(map(lambda x:abs(x-i),b))
    for j in range(n):
        w+=c[j]
    if w<ans:
        ans=w
print(ans)

### FIXED CODE ###

import statistics
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n):
    b[i]=a[i]-(i+1)
b.sort()
if n%2==1:
    m=statistics.median(b)
    b=list(map(lambda x:abs(x-m),b))
    ans=0
    for i in range(n):
        ans+=b[i]
else:
    m1=b[n//2]
    m2=b[n//2+1]
    k=list(map(lambda x:abs(x-m1),b))
    l=list(map(lambda x:abs(x-m2),b))
    ans1=0
    ans2=0
    for i in range(n):
        ans1+=k[i]
        ans2+=l[i]
    ans=min(ans1,ans2)
print(ans)