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

def countPairs(str_arr):
	count = 0
	for i in range(N):
		for j in range(i+1,N):
			if str_arr[i] == str_arr[j]:
				count += 1
	return count


N = int(input())
str_arr = []

for i in range(N):
	str = input()
	str_arr.append(sorted(str))

print(countPairs(str_arr))

### FIXED CODE ###

import operator as op
from functools import reduce
import math
	

def ncr(n, r):
	if n < r:
		return 0
	else :
		return (math.factorial(n)) / (math.factorial(n-r)*math.factorial(r))

def countPairs(str_arr, N):
	str_cnt = [0]
	str = str_arr[0]
	j = 0
	for i in range(N):
		if(str_arr[i]==str):
			str_cnt[j] += 1
		else:
			str = str_arr[i]
			j += 1
			str_cnt.append(0)
			str_cnt[j] += 1
	count = 0
	for i in range(len(str_cnt)):
		count += ncr(str_cnt[i],2)
	print(int(count))

def main():
	N = int(input())
	str_arr = []
	for i in range(N):
		str = input()
		str_arr.append(sorted(str))
	str_arr = sorted(str_arr)
	countPairs(str_arr, N)


main()
### BUGGY CODE ###

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

Sum = 0

for i in range(N - 1):
    for j in range(i + 1, N):
        Sum = (Sum + ((A[i] ^ A[j]) % ((10 ** 9) + 7))) % ((10 ** 9) + 7)

print(Sum)


### FIXED CODE ###

import math

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

Sum = 0
mod = (10 ** 9) + 7

for i in range(len(bin(max(A)))-2):
    Sum_1 = 0
    for j in range(N):
        #print(i, j)
        if ((A[j] >> i) & 1):
            Sum_1 += 1

    Sum_0 = N - Sum_1

    Sum = (Sum + ((Sum_0 * Sum_1) % mod * (2 ** i)) % mod) % mod
    # print(Sum_0,Sum_1)

print(Sum)
### BUGGY CODE ###

n = int(input())
a = 0
for i in range(n+1):
    if (str(i).count('7') + str(i).count('5') + str(i).count('3')) == len(str(i)) and '7' in str(i) and '5' in str(i) and '3' in str(i):
        a = a + 1
print(a)


### FIXED CODE ###

n = int(input())
def dfs(s):
        if int(s) > n:
                return 0
        ret = 0
        if s.count('7')>0 and s.count('5')>0 and s.count('3')>0:
            ret = 1
        for c in '753':
                ret += dfs(s + c)
        return ret
print(dfs('0'))
### BUGGY CODE ###

n = int(input()) #1行目のNを取得する
list = [input() for i in range(n)] #複数行の数値の入力を取得
lint = [int(s) for s in list]

ans = max(lint)
index = [i for i, x in enumerate(lint) if x == max(lint)]

if len(index) >= 2:
    for i in range(n):
        print(ans)
elif len(index) == 1:
    for i in range(0, index[0], 1):
        print(ans)
    a = lint.pop(index[0])
    print(max(lint))
    for i in range(index[0] + 1, n, 1):
        print(ans)

### FIXED CODE ###

n = int(input()) #1行目のNを取得する
list = [input() for i in range(n)] #複数行の数値の入力を取得
lint = [int(s) for s in list]

ans = max(lint)
index = lint.index(max(lint))
lint.remove(max(lint))
ans2 = max(lint)

if ans == ans2:
    for i in range(n):
        print(ans)
else:
    for i in range(0, index):
        print(ans)
    print(ans2)
    for i in range(index+1, n):
        print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

# n個の枠を作成
dp = [float("inf")] * n
# 初期値を0に
dp[0] = 0

#dp[i] =i番目まで来る最安の方法
for i in range(n):
    for j in range(1, min(i, k)+1):  # 上限が負にならないようにmin(i,k)で調整。+1でちゃんとrangeの癖を修正。
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [float("inf")] * n
dp[0] = 0

for i in range(n):
    for j in range(0, min(i, k)+1):
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[0]*(W+1) for _ in range(N+2)]
    #dp = [0]*(W+1)
    for i in range(N):
        for sum_w in range(W):
            if sum_w+w[i] <=W:
                dp[i+1][sum_w+w[i]] = max(dp[i][sum_w+w[i]], dp[i][sum_w]+v[i])
                #dp[sum_w+w[i]] = max(dp[sum_w+w[i]], dp[sum_w]+v[i])
            #dp[i+1][sum_w] = dp[i][sum_w]
            dp
        dp[i+2] = dp[i+1].copy()
    return max(dp[-1])


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]" 
    v = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    print(solve(N, W, w, v))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import copy

def solve(N, W, w, v):
    dp = [[0]*(W+1) for _ in range(N+2)]
    for i in range(N):
        for sum_w in range(W):
            if sum_w+w[i] <=W:
                dp[i+1][sum_w+w[i]] = max(dp[i][sum_w+w[i]], dp[i][sum_w]+v[i])
        dp[i+2] = copy.copy(dp[i+1])
    return max(dp[-1])

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
w,v=[], []
for i in wv:
    w.append(i[0])
    v.append(i[1])

print(solve(N, W, w, v))
### BUGGY CODE ###

MOD=10**9+7
S=input()

dp=[]
for i in range(len(S)+1):
  dp.append([0]*13)
dp[0][0]=1
#print(dp)

for i in range(1,len(S)+1):
  if S[i-1]=="?":
    for k in range(13):
      for j in range(10):
        dp[i][(10*k+j)%13]+=dp[i-1][k]
        dp[i][(10*k+j)%13]%=MOD
  else:
    si=int(S[i-1])
    for k in range(13):
      dp[i][(10*k+si)%13]+=dp[i-1][k]
      dp[i][(10*k+si)%13]%=MOD
    
#print(dp)
print(dp[-1][5])

### FIXED CODE ###

mod=10**9+7

S=input()

dp=[]
for i in range(len(S)):
  dp.append([0]*13)
#print(dp)

if S[-1]=="?":
  for j in range(10):
    dp[-1][j]=1
else:
  sj=int(S[-1])
  dp[-1][sj]=1
  
pow_mod=1
for i in range(1,len(S)):
  pow_mod*=10
  pow_mod%=13
  if S[-i-1]=="?":
    for k in range(13):
      for j in range(10):
        dp[-i-1][(k+j*pow_mod)%13]+=dp[-i][k]
        dp[-i-1][(k+j*pow_mod)%13]%=mod
  else:
    sj=int(S[-i-1])
    for k in range(13):
      dp[-i-1][(k+sj*pow_mod)%13]+=dp[-i][k]
      dp[-i-1][(k+sj*pow_mod)%13]%=mod
    
#print(dp)
print(dp[0][5]%mod)
### BUGGY CODE ###


nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

H, W = nl()
grid = []
for i in range(H):
    grid.append(s())

yoko = [[0] * W for h in range(H)]
for row in range(H):
    count = 0
    for col in range(W):
        if grid[row][col] == '.':
            count += 1
            yoko[row][col] = count
        else:
            count = 0

    count = 0
    for col in range(W-1, -1, -1):
        if yoko[row][col] > 0:
            count = max(count, yoko[row][col])
            yoko[row][col] = count
        else:
            count = 0

tate = [[0] * W for h in range(H)]
for col in range(W):
    count = 0
    for row in range(H):
        if grid[row][col] == '.':
            count += 1
            tate[row][col] = count
        else:
            count = 0

    count = 0
    for row in range(H-1, -1, -1):
        if tate[row][col] > 0:
            count = max(count, tate[row][col])
            tate[row][col] = count
        else:
            count = 0

res = 0
for row in range(H):
    for col in range(W):
        res = max(res, yoko[row][col] + tate[row][col] - 1)

print(res)




### FIXED CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

H, W = nl()
grid = []
for i in range(H):
    grid.append(s())

ups = [[0]*W for j in range(H)]
downs = [[0]*W for j in range(H)]
lefts = [[0]*W for j in range(H)]
rights = [[0]*W for j in range(H)]

for col in range(W):
    p = 0
    for row in range(H):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        ups[row][col] = p

    p = 0
    for row in range(H-1, -1, -1):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        downs[row][col] = p

for row in range(H):
    p = 0
    for col in range(W):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        lefts[row][col] = p

    p = 0
    for col in range(W-1, -1, -1):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        rights[row][col] = p

res = 0
for row in range(H):
    for col in range(W):
        res = max(res, ups[row][col] + downs[row][col] + lefts[row][col] + rights[row][col] -3)
print(res)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            a = l[i]
            b = l[j]
            c = l[k]
            if a<b+c and b<c+a and c<a+b:
                cnt+=1
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
cnt = 0
l = sorted(l)
for i in range(n):
    for j in range(i+1,n):
        d = l[i]+ l[j]
        cnt +=bisect.bisect_left(l,d) - (j+1)
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    words = {}
    for _ in range(n):
        a = input()
        if a in words:
            words[a] += 1
        else:
            words[a] = 1
    results = [kv[0] for kv in words.items() if kv[1] == max(words.values())]
    results.sort()
    print(' '.join(map(str, results)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    words = {}
    for _ in range(n):
        a = input()
        if a in words:
            words[a] += 1
        else:
            words[a] = 1
    max_val = 0
    results = []
    for i in words.keys():
        if words[i] > max_val:
            max_val = words[i]
            results = []
            results.append(i)
        elif words[i] == max_val:
            results.append(i)

            # results = [key
            #            for key in words.keys() if words[key] == max(words.values())]
            # results.sort()
    results.sort()
    print('\n'.join(map(str, results)))


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

from collections import deque

n, m = map(int, input().split())
uv  =[[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    uv[u - 1].append(v - 1)
s, t = map(int, input().split())
s -= 1
t -= 1
uv2 = [[] for _ in range(n)]
uv3 = [[] for _ in range(n)]

for i, lst in enumerate(uv):
    for j in lst:
        lst2 = uv[j]
        for k in lst2:
            uv2[i].append(k)
            
for i, lst in enumerate(uv):
    for j in lst:
        lst2 = uv2[j]
        for k in lst2:
            uv3[i].append(k)

queue = deque()
queue.append(s)
queue.append(1)
check = [False for _ in range(n)]
check[s] = True

while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    for next_pos in uv3[pos]:
        if next_pos == t:
            print(ans)
            exit()
        if check[next_pos]:
            continue
        check[next_pos] = True
        queue.append(next_pos)
        queue.append(ans + 1)
print(-1)
    

### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
uv  =[[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    uv[u - 1].append(v - 1)
s, t = map(int, input().split())
s -= 1
t -= 1

queue = deque()
queue.append(s)
queue.append(1)
queue.append(0)
check = [[False for _ in range(3)] for _ in range(n)]
check[s][0] = True

while queue:
    pos = queue.popleft()
    ans = queue.popleft()
    kkp = queue.popleft()
    for next_pos in uv[pos]:
        if next_pos == t and kkp == 2:
            print(ans // 3)
            exit()
        if check[next_pos][(kkp + 1) % 3]:
            continue
        check[next_pos][(kkp + 1) % 3] = True
        queue.append(next_pos)
        queue.append(ans + 1)
        queue.append((kkp + 1) % 3)
print(-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = int(input())
tempM = 0
M = []

for i in range(N):
    for p in range(N):
        temp = p % (i+1)
        if temp > tempM:
            tempM = temp
    M.append(tempM)

print(sum(M))

### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())

print(int(N*(N-1)//2))
### BUGGY CODE ###

#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))


N=input1()
p=input_array()
count=0
for i in range(N):
	flag=True
	for j in range(len(p[:i+1])):
		if p[i]<=p[j]:
			flag=True
		else:
			flag=False
			break
	if flag:
		count+=1
print(count)








### FIXED CODE ###

#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))


N=input1()
p=input_array()
count=0
min_int=0
for i in range(N):
	num=p[i]
	if i==0:
		min_int=num
		count+=1
	elif num<=min_int:
		min_int=num
		count+=1
		
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

n = int(input())
edge = [[[] for i in range(2)] for j in range(n)]
dp = [-1] * n
for i in range(n - 1):
    a, b, c = map(int, input().split())
    edge[a - 1][0].append(b - 1)
    edge[a - 1][1].append(c)
    edge[b - 1][0].append(a - 1)
    edge[b - 1][1].append(c)


def distance(x, prev, d):
    dp[x] = d
    for i, j in zip(edge[x][0], edge[x][1]):
        if i == prev:
            continue
        if dp[i] != -1:
            continue
        distance(i, x, d + j)
    return

q, k = map(int, input().split())
k -= 1

ans = []
distance(k, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    ans.append(dp[x - 1] + dp[y - 1])

for i in range(q):
    print(ans[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

n = int(input())
edge = [[[] for i in range(2)] for j in range(n)]
dp = [-1] * n
for i in range(n - 1):
    a, b, c = map(int, input().split())
    edge[a - 1][0].append(b - 1)
    edge[a - 1][1].append(c)
    edge[b - 1][0].append(a - 1)
    edge[b - 1][1].append(c)


def distance(x, prev, d):
    dp[x] = d
    for i, j in zip(edge[x][0], edge[x][1]):
        if i == prev:
            continue
        if dp[i] != -1:
            continue
        distance(i, x, d + j)
    return

q, k = map(int, input().split())
k -= 1

ans = []
distance(k, -1, 0)
for i in range(q):
    x, y = map(int, input().split())
    ans.append(dp[x - 1] + dp[y - 1])

for i in range(q):
    print(ans[i])
### BUGGY CODE ###

def reduce(n):
  if n == 0:
    return 2
  
  if n == 1:
    return 1
  
  return reduce(n-1) + reduce(n-2)

print(reduce(int(input())))

### FIXED CODE ###

n = int(input())

l = [0 for i in range(n+1)]
l[0], l[1] = 2, 1
for i in range(2, n+1):
  l[i] = l[i-1]+l[i-2]

print(l[-1])
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
new_A = set([abs(ai-aj) for aj in A for ai in A]) - {0}
max_a = max(A)
set_A = set(A)
if k in A:
    print("POSSIBLE")
elif max_a >= k:
    if new_A - set_A == set():
        print("IMPOSSIBLE")
    else:
        print("POSSIBLE")
elif max_a < k:
    print("IMPOSSIBLE")


### FIXED CODE ###

from fractions import gcd
N, K = map(int, input().split())
A = list(map(int, input().split()))
if K in A:
  print('POSSIBLE')
elif K > max(A):
  print('IMPOSSIBLE')
else:
  A_gcd = A[0]
  for i in range(1, N):
    A_gcd = gcd(A_gcd, A[i])

  if K % A_gcd == 0:
    print('POSSIBLE')
  else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N = int(input())
S = list(input())
count_list = []
for i in range(N):
  S_l = S[:i]
  S_r = S[i+1:]
  count = S_l.count("W") + S_r.count("E")
  count_list.append(count)
print(min(count_list))

### FIXED CODE ###

N = int(input())
S = list(input())
count_E = S.count("E")
count_W = 0
ans = count_E
for i in range(N):
    if S[i] == "E":
        count_E -= 1
    if S[i-1] == "W" and i != 0:
        count_W += 1
    if count_E + count_W < ans :
        ans = count_E + count_W
print(ans)
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())

M = r2+c2+10#1000010
mod = 10**9+7

f    = [1]*M
p = 1
for i in range(1, M):
    p = p*i%mod
    f[i] = p
    #finv[i] = pow(p, mod-2, mod)

finv = [1]*M
p = finv[-1] = pow(f[-1], mod-2, mod)
for i in range(M-2, 0, -1):
    p = p*(i+1)%mod
    finv[i] = p


def comb(n, k):
    return f[n] * finv[n-k] * finv[k] % mod

def count(R,C):
    ret = ((1<<R+C+1)-1) % mod

    for c in range(C):
        x1 = comb(R+c, c)
        x2 = ((1<<C-c)-1) % mod
        ret = (ret-x1*x2) % mod

    for r in range(R):
        x1 = comb(C+r, r)
        x2 = ((1<<R-r)-1) % mod
        ret = (ret-x1*x2) % mod

    return ret

ans = count(r2, c2) + count(r1-1, c1-1) - count(r2, c1-1) - count(r1-1, c2)
ans %= mod
print(ans)


### FIXED CODE ###

r1, c1, r2, c2 = map(int, input().split())

M = r2+c2+10#1000010
mod = 10**9+7

f    = [1]*M
p = 1
for i in range(1, M):
    p = p*i%mod
    f[i] = p
    #finv[i] = pow(p, mod-2, mod)

finv = [1]*M
p = finv[-1] = pow(f[-1], mod-2, mod)
for i in range(M-2, 0, -1):
    p = p*(i+1)%mod
    finv[i] = p

g = [0]*M
p = 0
for i in range(1, M):
  g[i] = p = ((p+1)*2-1)%mod

def comb(n, k):
    return f[n] * finv[n-k] * finv[k] % mod

def count(R,C):
    ret = g[R+C+1] % mod

    for c in range(C):
        x1 = comb(R+c, c)
        x2 = g[C-c]
        ret = (ret-x1*x2) % mod

    for r in range(R):
        x1 = comb(C+r, r)
        x2 = g[R-r]
        ret = (ret-x1*x2) % mod

    return ret

ans = count(r2, c2) + count(r1-1, c1-1) - count(r2, c1-1) - count(r1-1, c2)
ans %= mod
print(ans)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(n):
    for j in range(i+1,n):
        if A[i]+A[j]==abs(i-j):
            ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
dic={}
ans=0
for i in range(n):
    x=i-A[i]
    y=i+A[i]
    if x in dic:
        ans+=dic[x]
    if y in dic:
        dic[y]+=1
    else:
        dic[y]=1
print(ans)
### BUGGY CODE ###

s=input()
len_s=len(s)
mod=10**9+7
dp=[[0]*13 for i in range(len_s)]

if s[-1]!='?':
    dp[0][int(s[-1])%13]=1
else:
    for i in range(10):
        dp[0][i]=1

for i in range(1,len_s):

    if s[-(i+1)]!='?':
        temp_S=int(s[-(i+1)])
        amari=(temp_S*10**i)%13
        for j in range(13):
            dp[i][(amari+j)%13]=(dp[i][(amari+j)%13]+dp[i-1][j])%mod

    else:
        for k in range(10):
            amari=(k*10**i)%13
            for l in range(13):
                dp[i][(amari+l)%13]=(dp[i][(amari+l)%13]+dp[i-1][l])%mod
#print(*dp,sep='\n')
print(dp[-1][5]%mod)


### FIXED CODE ###

s=input()
len_s=len(s)
mod=10**9+7
dp=[[0]*13 for i in range(len_s)]

if s[-1]!='?':
    dp[0][int(s[-1])%13]=1
else:
    for i in range(10):
        dp[0][i]=1

a=1
for i in range(1,len_s):
    a=10*a%13
    if s[-(i+1)]!='?':
        temp_S=int(s[-(i+1)])
        amari=(temp_S*a)%13
        for j in range(13):
            dp[i][(amari+j)%13]+=dp[i-1][j]%mod

    else:
        for k in range(10):
            amari=(k*a)%13
            for l in range(13):
                dp[i][(amari+l)%13]+=dp[i-1][l]%mod
#print(*dp,sep='\n')
print(dp[-1][5]%mod)
### BUGGY CODE ###

import numpy as np

N, Q = (int(x) for x in input().split())

dic = {}
for i in range(N) :
    dic[i+1] = []

for i in range(N-1) :
    a, b = (int(x) for x in input().split())
    dic[a].append(b)
    for n in dic.keys() :
        if a in dic[n] :
            dic[n].append(b)

SUM = np.zeros(N, dtype=np.int)

for i in range(Q) :
    p, x = (int(x) for x in input().split())
    SUM[p-1] = SUM[p-1] + x
    for n in dic[p] :
        SUM[n-1] = SUM[n-1] + x

print(' '.join(map(str, SUM)))

### FIXED CODE ###


import numpy as np

N, Q = (int(x) for x in input().split())

dic = {}

for i in range(N-1) :
    #a, b = (int(x) for x in input().split())
    a, b = map(int,input().split())
    dic[b] = a

#SUM = np.zeros(N, dtype=np.int)
SUM = [0]*N

for i in range(Q) :
    #p, x = (int(x) for x in input().split())
    p, x = map(int,input().split())
    SUM[p-1] = SUM[p-1] + x

for i in range(N-1) :
    SUM[i+1] += SUM[dic.get(i+2)-1]

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

memo={}
def calc(A, b):
    score = memo.get(b, None)
    if not score is None:
        return score
    score = sum(abs(a-b) for a in A)
    memo[b] = score
    return score

def findmin(A, l, u):
    if l + 1 == u:
        return min(calc(A, l), calc(A, u))
    if l == u:
        return calc(A, l)
    d = (u-l)//3
    if d == 0:
        return min(calc(A, i) for i in range(l, u+1))
    left, right = l + d, u - d
    sl = calc(A, left) 
    sr = calc(A, right) 
    if sl > sr:
        return findmin(A, left, u)
    else:
        return findmin(A, l, right)

def solve(A):
    A = sorted(a-(i+1) for i, a in enumerate(A))
    return findmin(A, A[0], A[-1])

#solve(list(range(1000, 2*10**5)))
N = int(input())
A = [int(x) for x in input().split()]

#abs(A1-(b+1)) + abs(Ai-(b-i)) + abs(AN-(b-N))


# b1 = A[0]    ならば (A[i]-b1) >= 0
# b2 = A[0] -1 ならば (A[i]-b2) > (A[i]-b1) >= 0 なので、スコアは大きくなる

# b = A[-1] ならば (A[i]-b) <= 0

print(solve(A))



### FIXED CODE ###

memo={}
def calc(A, b):
    score = memo.get(b, None)
    if not score is None:
        return score
    score = sum(abs(a-b) for a in A)
    memo[b] = score
    return score

c = 0
def findmin(A, l, u):
    global c
    c+=1
    d = (u-l)//3
    if d == 0:
        return min(calc(A, i) for i in range(l, u+1))
    left, right = l + d, u - d
    sl = calc(A, left) 
    sr = calc(A, right) 
    if sl > sr:
        return findmin(A, left, u)
    else:
        return findmin(A, l, right)

def solve(A):
    B= [0] * len(A)
    l = A[0]
    u = A[0]
    for i, a in enumerate(A):
        b = a-(i+1)
        l = min(l, b)
        u = max(u, b)
        B[i] = b
    #A = [a-(i+1) for i, a in enumerate(A)]
    return findmin(B, l, u)

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

#abs(A1-(b+1)) + abs(Ai-(b-i)) + abs(AN-(b-N))


# b1 = A[0]    ならば (A[i]-b1) >= 0
# b2 = A[0] -1 ならば (A[i]-b2) > (A[i]-b1) >= 0 なので、スコアは大きくなる

# b = A[-1] ならば (A[i]-b) <= 0
print(solve(A))
### BUGGY CODE ###

from collections import deque
n=int(input())
a=list(map(int,input().split()))
d=deque()
for i in range(1,n):
  d.append((i+1)-a[i])
cnt=0
for i in range(n-1):
  cnt+=d.count(a[i]+(i+1))
  d.popleft()
print(cnt)

### FIXED CODE ###

from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
d=defaultdict(int)
cnt=0
for i in range(n):
  cnt+=d[i-a[i]]
  d[a[i]+i]+=1
print(cnt)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=20202020200
for i in range(N):
    tmp=abs(sum(A[:i])-sum(A[i:N]))
    if tmp<ans:
        ans=tmp
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=20202020200
sum_A=0
sum_B=sum(A)
for i in range(N):
    sum_A+=A[i]
    sum_B-=A[i]
    tmp=abs(sum_A-sum_B)
    if tmp<ans:
        ans=tmp
print(ans)
### BUGGY CODE ###

import sys
def main():
    s=sys.stdin.readline().strip()
    d,c={0:1},0
    for i in range(len(s)):
        k=int(s[-1-i:])%2019
        d[k]=d[k]+1 if k in d else 1
    for v in d.values():c+=v*(v-1)//2
    print(c)
if __name__=='__main__':main()

### FIXED CODE ###

import sys
def main():
    s=sys.stdin.readline().strip()
    x=[0 for _ in [0]*2020]
    x[0],c=1,0
    m,d=0,1
    for i in reversed(s):
        m+=(int(i)*d)
        x[m%2019]+=1
        d=(d*10)%2019
    for v in x:c+=v*(v-1)//2
    print(c)
if __name__=='__main__':main()