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

# https://atcoder.jp/contests/dp/tasks/dp_n
import numpy as np

N = int(input())
xs = np.array([0] + [int(s) for s in input().split()])
acc = np.add.accumulate(xs)

dp = np.zeros((N, N + 1), dtype=np.int64)

for i in range(N):
    dp[i][i + 1] = 0

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = np.min([dp[i][k] + dp[k][j] for k in range(i + 1, j)])
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])


### FIXED CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

dp = [[INF] * (N + 1) for _ in range(N)]

for i in range(N):
    dp[i][i + 1] = 0

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

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

n, k, q = map(int, input().split())
quiz = [int(input()) for i in range(q)]
point = [k]*n
for i in quiz:
  point = list(map(lambda x: x-1, point))
  point[i-1] += 1
[print("Yes") if i > 0 else print("No") for i in point]

### FIXED CODE ###

n, k, q = map(int, input().split())
quiz = [int(input()) for i in range(q)]
point = [k-q]*n
for i in quiz:
  point[i-1] += 1
[print("Yes") if i > 0 else print("No") for i in point]
'''
1. あらかじめ全員のポイントを Q 減らしておく (つまり，開始時点のポイントは K − Q)．
2. Q 回の正解それぞれに対して，正解者のポイントを 1 増やす．

リストの中身すべてに計算すると「リスト要素」＊「ループ回数」の計算量になる
'''
### BUGGY CODE ###

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

BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
    
def reverse_insort(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it reverse-sorted assuming a
    is reverse-sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    a.insert(lo, x)

cards = A[:]
cards  =sorted(cards, reverse=True)

opes = BC[:]
opes =sorted(opes, reverse=True, key=lambda x:x[1])
#print(opes)




for b, c in opes:
    if cards[-1] > c:
        break
    for _ in range(b):
        if cards[-1] > c:
            break
        else:
            cards.pop()
            reverse_insort(cards, c)
            
ans = sum(cards)
#print(cards)
print(ans)
            


### FIXED CODE ###

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

BC = []
for _ in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))
    
cards = A[:]
opes = BC[:]

cards_dict = {}

for c in cards:
    if c in cards_dict:
        cards_dict[c] += 1
    else:
        cards_dict[c] = 1

for b, c in opes:
    if c in cards_dict:
        cards_dict[c] += b
    else:
        cards_dict[c] = b
        
cards_dict = sorted(cards_dict.items(), reverse=True)
#print(cards_dict)

num = 0
ans = 0
for k, v in cards_dict:
    if num + v > N:
        ans += k * (N-num)
        num = N
    else:
        ans +=  k * v
        num += v
    if num == N:
        break
        
print(ans)
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ab=sorted([x+y for x in a for y in b],reverse=True)[:k]
abc=sorted([x+y for x in ab for y in c],reverse=True)[:k]
for i in abc:
  print(i)

### FIXED CODE ###

from heapq import nlargest
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ab=nlargest(k,(x+y for x in a for y in b))
abc=nlargest(k,(xy+z for xy in ab for z in c))
for i in abc:
  print(i)
### BUGGY CODE ###

#coding:utf-8
import bisect,math
A,B,Q=map(int,raw_input().split())
s=[]
t=[]
for a in range(A):
    s.append(input())
for a in range(B):
    t.append(input())
buf=[]    
for _ in xrange(Q):
    x=input()
    sl=bisect.bisect_left(s,x)-1
    sr=bisect.bisect_left(s,x)
    tl=bisect.bisect_left(t,x)-1
    tr=bisect.bisect_left(t,x)
    ans=float("inf")
    if sl!=-1 and tl!=-1:
        A=max(s[sl],t[tl])
        B=min(s[sl],t[tl])
        L=abs(x-A)+abs(A-B)
        ans=min(ans,L)
    if sl!=-1 and tr!=len(t):
        L=abs(x-s[sl])*2 + abs(t[tr]-x)        
        ans=min(ans,L)
        ans=min(ans,abs(x-s[sl])+abs(t[tr]-x)*2)
    if tl!=-1 and sr!=len(s):
        ans=min(ans,abs(x-t[tl])*2+abs(s[sr]-x))
        ans=min(ans,abs(x-t[tl])+abs(s[sr]-x)*2)
    if tr!=len(t) and sr!=len(s):
        A=min(s[sr],t[tr])
        B=max(s[sr],t[tr])
        L=abs(A-x)+abs(B-A)
        ans=min(ans,L)
    buf.append(str(ans))
print "\n".join(buf)
    

### FIXED CODE ###

#coding:utf-8
import bisect,sys
A,B,Q=map(int,raw_input().split())
s=[0]*A
t=[0]*B
for i in range(A):    
    s[i]=int(sys.stdin.readline())
for i in range(B):
    t[i]=int(sys.stdin.readline())
buf=[]
def f(x):
    sl=bisect.bisect_left(s,x)-1
    sr=sl+1
    tl=bisect.bisect_left(t,x)-1
    tr=tl+1
    ans=float("inf")
    if sl!=-1 and tl!=-1:
        A=max(s[sl],t[tl])
        B=min(s[sl],t[tl])
        L=abs(x-A)+abs(A-B)
        ans=min(ans,L)
    if sl!=-1 and tr!=len(t):
        L=abs(x-s[sl])*2 + abs(t[tr]-x)        
        ans=min(ans,L)
        ans=min(ans,abs(x-s[sl])+abs(t[tr]-x)*2)
    if tl!=-1 and sr!=len(s):
        ans=min(ans,abs(x-t[tl])*2+abs(s[sr]-x))
        ans=min(ans,abs(x-t[tl])+abs(s[sr]-x)*2)
    if tr!=len(t) and sr!=len(s):
        A=min(s[sr],t[tr])
        B=max(s[sr],t[tr])
        L=abs(A-x)+abs(B-A)
        ans=min(ans,L)
    return str(ans)

I=[0]*Q
for i in xrange(Q):
    I[i]=int(sys.stdin.readline())
r=map(f,I)
print("\n".join(r))
### BUGGY CODE ###

import heapq
import sys

class rode():
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def __lt__(self, other):
        return self.y < other.y
    def __gt__(self, other):
        return other > self
    def __le__(self, other):
        return not(other > self)
    def __ge__(self, other):
        return not(self > other)

n,m = map(int,input().split())
da = [[[i-1,0]] for i in range(n)]
da[0] = []
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
pq=[]
ju = [False for i in range(n)]
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, rode(i[0],i[1]))
while(len(pq)):
    now = heapq.heappop(pq)
    if now.x == n-1:
        print(now.y)
        sys.exit()
    if ju[now.x]:
        continue
    ju[now.x] = True
    for i in da[now.x]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,rode(i[0],now.y+i[1]))
print(-1)

### FIXED CODE ###

import heapq
import numpy as np
import sys

n,m = map(int,input().split())
da = [[] for i in range(n)]
for i in range(1,n):
    da[i].append([i-1,0])
for i in range(m):
    l,r,c = map(int,input().split())
    da[l-1].append([r-1,c])
pq=[]
ju = np.zeros(n,dtype=bool)
ju[0] = True
for i in da[0]:
    heapq.heappush(pq, [i[1],i[0]])
while(len(pq)):
    now = heapq.heappop(pq)
    if now[1] == n-1:
        print(now[0])
        sys.exit()
    if ju[now[1]]:
        continue
    ju[now[1]] = True
    for i in da[now[1]]:
        if ju[i[0]]:
            continue
        heapq.heappush(pq,[now[0]+i[1],i[0]])
print(-1)
### BUGGY CODE ###

n=int(input())
ans=1
for i in range(1,n+1):
    ans=ans*i
print(ans%(10**9+7)) 

### FIXED CODE ###

import math
x = int(input())
i=math.factorial(x)
print(i%(10**9+7))
### BUGGY CODE ###

from math import factorial
def com(n,r):
    if n-r<0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

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


all = 0
for i in se_:
    all += com(A.count(i),2)
    

for i in A:
    final=0
    final = all - com(A.count(i),2) + com(A.count(i)-1,2)
    print(final)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
se_ = Counter(A)
key = se_.keys()
 
 
all = 0
for i in key:
    all += se_[i]*(se_[i]-1)//2
    
 
for i in A:
    final=0
    final = all -se_[i]+1
    print(final)
### BUGGY CODE ###

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

while(len(A)!=0):
  if A.count(A[0]) >1:
    print("NO")
    exit(0)
  A.pop(0)
  
print("YES")


### FIXED CODE ###

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

A=sorted(A)

for i in range(0,N):
  if len(A) > i+1:
    if A[i] == A[i+1]:
      print("NO")
      exit(0)
print("YES")
### BUGGY CODE ###

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

now = 1
for i in range(n):
    if i < k:
        now *= a[i]
        continue
    old = now
    now = (now / a[i-k]) * a[i]
    print("Yes" if now > old else "No")


### FIXED CODE ###

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

i = k
# while i < k:
#     now *= a[i]
#     i += 1
while i < n:
    old = a[i-k]
    now = a[i]
    print("Yes" if now > old else "No")
    i += 1
    # old = now
    # now = (now / a[i-k]) * a[i]
    # print("Yes" if now > old else "No")
    # i += 1
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

def bfs(start, goal, H, W):
    visited = [False for _ in range(H * W)]
    import queue
    q = queue.Queue()
    q.put((start[0], start[1], 0))
    while not q.empty():
        (i, j, dist) = q.get()
        if (i, j) == goal:
            return dist
        visited[i * W + j] = True 
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0 or dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if visited[(i + dy) * W + j + dx]:
                    continue
                q.put((i + dy, j + dx, dist + 1))
    return -1

ans = 0
s = set()
for i in range(H * W):
    start = (i // W, i % W)
    if S[start[0]][start[1]] == '#':
        continue
    for j in range(H * W):
        goal = (j // W, j % W)
        if S[goal[0]][goal[1]] == '#':
            continue
        if start == goal:
            continue
        if (goal, start) in s:
            continue
        ans = max(ans, bfs(start, goal, H, W))
        s.add((start, goal))
print(ans)


### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
 
from functools import reduce
# from math import *
from fractions import *
H, W = map(int, readline().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = readline().decode().strip()

from collections import deque
def bfs(start, H, W):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    q = deque([start])
    dist[start[0] * W + start[1]] = 0
    while q:
        (i, j) = q.popleft()
        d = dist[i * W + j]
        for dy in range(-1, 2):
            for dx in range(-1, 2):
                if dx * dy != 0:
                    continue
                if dx == dy:
                    continue
                if i + dy < 0 or i + dy >= H or j + dx < 0 or j + dx >= W:
                    continue
                if S[i + dy][j + dx] == '#':
                    continue
                if dist[(i + dy) * W + j + dx] != INF:
                    continue
                dist[(i + dy) * W + j + dx] = d + 1
                q.append((i + dy, j + dx))
    return max(x for x in dist if x < INF)

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        start = (i, j)
        ans = max(ans, bfs(start, H, W))
print(ans)
### BUGGY CODE ###

k,s = map(int ,input().split())
count=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                count+=1
print(count)      

### FIXED CODE ###

k,s = map(int ,input().split())
count=0
for x in range(k+1):
    for y in range(k+1):
        if 0<=s-(x+y)<=k:
            count+=1
print(count)
### BUGGY CODE ###

s = input()
q = int(input())


inv = False
mae = ''
usiro = ''

for _ in range(q):
    tmp = list(input().split())
    if tmp == ['1']:
        inv = not inv

    elif tmp[1] == '1' and not inv:
        mae = tmp[2] + mae
    elif tmp[1] == '2' and not inv:
        usiro = usiro + tmp[2]
    elif tmp[1] == '1' and inv:
        usiro = usiro + tmp[2]
    elif tmp[1] == '2' and inv:
        mae = tmp[2] + mae

    # print(mae,s,usiro)

ans = ''.join(mae) + s + ''.join(usiro)

if inv:
    ans = ans[::-1]

print(ans)

### FIXED CODE ###

s = input()
q = int(input())

inv = False
mae = ''
usiro = ''

for _ in range(q):
    tmp = input()
    if tmp[0] == '1':
        inv = not inv

    else:
        _,f,c = tmp.split()

        if f == '1' and not inv:
            mae += c
        elif f == '2' and not inv:
            usiro += c
        elif f == '1' and inv:
            usiro += c
        elif f == '2' and inv:
            mae += c

    # print(mae,s,usiro)

ans = mae[::-1] + s + usiro

if inv:
    ans = ans[::-1]

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

N = int( input() )
c_list = []
for i in range(N):
    c_list.append( int( input() ) )
for i in range(N):
    a = c_list[:]
    del a[i]
    print( max(a) )

### FIXED CODE ###

N = int( input() )
c_list = []
for i in range(N):
    c_list.append( int( input() ) )
    
a = c_list[:]
a.sort()
ma = a[ N - 1 ]

for i in range(N):
    t = c_list[i]
    if t == ma:
        print(a[N - 2])
    else:
        print(ma)
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

N, x, y = map(int, input().split())
graph = [[0 for i in range(N)] for i in range(N)]

for i in range(N-1):
    graph[i][i+1] = 1
    graph[i+1][i] = 1

graph[x-1][y-1] = 1
graph[y-1][x-1] = 1

graph = csr_matrix(graph)

result = floyd_warshall(csgraph=graph, directed=False)

ans = {i+1:0 for i in range(N)}

for i in range(N):
    for j in range(N):
        if result[i,j]  == 0:
            continue
        ans[int(result[i, j])] = ans[int(result[i,j])] + 1

for i in range(1, N):
    print(ans[i]//2)

### FIXED CODE ###

N, X, Y = map(int, input().split())
from itertools import combinations

ans = {i+1:0 for i in range(N)}
for a, b in combinations(range(1, N+1), 2):
    t = b - a
    if a <= X:
        t = min(t, X - a + 1 + abs(Y - b))
    elif a <= Y:
        t = min(t, abs(a - X) + 1 + abs(Y - b))
    ans[t] += 1

for i in range(1, N):
    print(ans[i])
### BUGGY CODE ###

[X,K,D]=[int(_) for _ in input().split()]
X=abs(X)
Y=X//D
if K>Y:
  K-=Y
  X-=Y*D
#print(X,K,D)
X/=D
for _ in range(K//2):
  X = min([abs(X-2), abs(X), abs(X+2)])
  #print(X)
if K%2 == 1:
  X = min([abs(X-1), abs(X+1)])
  #print(X)
print(abs(int(X*D)))

### FIXED CODE ###

[X,K,D]=[int(_) for _ in input().split()]
X=abs(X)
Y=X//D
if Y <= K:
  X-=Y*D
  if (K-Y)%2 != 0:
    X = abs(X-D) if abs(X-D) < abs(X+D) else abs(X+D)
else:
  X-=K*D
print(X)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    b[i]=0
  else:
    b[i]+=b[i-1]
    if i>1:b[i]+=b[i-2]
print(b[n]%(10**9+7))

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
a = set(int(input()) for _ in range(m))
#for i in range(m):
#  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    continue
  x=b[i-1]
  if i>1:x+=b[i-2]
  b[i]=x
print(b[n]%(10**9+7))
### BUGGY CODE ###

S=input()
T=input()
d=[[] for i in range(26)]
for i,c in enumerate(S):
    d[ord(c)-ord('a')].append(i)
d2=[[] for i in range(26)]
for i,c in enumerate(T):
    d2[ord(c)-ord('a')].append(i)
d=sorted([x for x in d if x],key=lambda x:x[0])
d2=sorted([x for x in d2 if x],key=lambda x:x[0])
f=0
if len(d)==len(d2):
    f=1
    for i in range(len(d)):
        if len(d[i])!=len(d2[i]):
            f=0
        else:
            for j in range(len(d[i])):
                if d[i]!=d2[i]:
                    f=0
print(['No','Yes'][f])

### FIXED CODE ###

S=input()
T=input()
d=[[] for i in range(26)]
for i,c in enumerate(S):
    d[ord(c)-ord('a')].append(i)
d2=[[]for i in range(26)]
for i,c in enumerate(T):
    d2[ord(c)-ord('a')].append(i)
print(['No','Yes'][set((tuple(x) for x in d))==set((tuple(x) for x in d2))])
### BUGGY CODE ###

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

Asp = []
for a in As:
    Asp.append(a >> 1)

from fractions import gcd
import functools

l = functools.reduce(lambda a, b: a * b // gcd(a, b), Asp)

i = 2
while l & (i - 1) == 0:
    i *= 2
i = i // 2 - 1

fg = False
if i > 0:
    for a in Asp:
        if a & i > 0:
            fg = True
            break

if fg:
    print(0)
else:
    print(M // l - M // (l * 2))

### FIXED CODE ###

N, M = map(int, input().split())
As = list(map(lambda a: int(a) >> 1, input().split()))

from fractions import gcd

l = As[0]
for a in As:
    l = l * a // gcd(l, a)
    if l > M:
        break

if l <= M:
    i = 2
    while l & (i - 1) == 0:
        i <<= 1
    i = (i >> 1) - 1

    fg = False
    if i > 0:
        for a in As:
            if a & i > 0:
                fg = True
                break

    if fg:
        print(0)
    else:
        print(M // l - M // (l * 2))
else:
    print(0)
### BUGGY CODE ###

N = int(input())
s = [sorted(list(input())) for i in range(N)]
count = 0
for i in range(N):
    for j in range(N):
        if s[i] == s[j]:
            count += 1
print(int((count-N)/2))

### FIXED CODE ###

N = int(input())
s = {}
ans = 0
for i in range(N):
    a = "".join(sorted(input()))
    if a not in s:
        s.setdefault(a,0)
    else:
        s[a] += 1
        ans += s[a]
print(ans)
### BUGGY CODE ###

n=int(input())
p=sorted(list(map(int,input().split())))
s=set()
m = 10**6+1
a=[True for _ in range(m)]
prev = 0
for x in p:
    if prev == x:
        s.discard(x)
        continue
    if a[x]:
        s.add(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
    prev=x

print(len(s))

### FIXED CODE ###

n=int(input())
p=sorted(list(map(int,input().split())))
s=set()
m = 10**6+1
a=[True for _ in range(m)]
prev = 0
for x in p:
    if prev == x:
        s.discard(x)
        continue
    if a[x]:
        s.add(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
    prev=x

print(len(s))
### BUGGY CODE ###

N, P = [int(_c) for _c in input().split(" ")]
 
if N == 1:
    print(P)
else:
    _max = 1
    M = int(P ** (1 / N))
    for i in range(1, M + 2):
        var = i ** N
        if P % var == 0:
            _max = i
 
    print(_max)

### FIXED CODE ###

N, P = [int(_c) for _c in input().split(" ")]

if N == 1:
    print(P)
else:
    _max = 1
    M = int(P ** (1 / N) + 1.0 * 1e-9)
    for i in range(1, M + 1):
        if P % (i ** N) == 0:
            _max = i

    print(_max)
### BUGGY CODE ###

import numpy as np

N = int(input())
a = np.asarray(list(map(int, input().split())))
Q = int(input())

for i in range(Q):
    b, c = map(int, input().split())
    a[a == b] = c
    print(np.sum(a))

### FIXED CODE ###

from collections import Counter

N = int(input())
a = Counter(map(int, input().split()))
Q = int(input())

sum_a = sum(a.elements())

for i in range(Q):
    b, c = map(int, input().split())
    a[c] += a[b]
    sum_a += (c-b) * a[b]
    a[b] = 0
    print(sum_a)
### BUGGY CODE ###

def main():
    from collections import deque

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = [[-1] * (N + 1) for _ in range(N + 1)]  # 離席コスト,J字にコスト-1の区画を設ける
    for r in range(N):
        dr = min(r, N - 1 - r)
        for c in range(N):
            dc = min(c, N - 1 - c)
            H[r][c] = min(dr, dc)
    S = [[1] * N for _ in range(N)]  # 着席

    ans = 0
    for pi in p:
        pi_r, pi_c = divmod(pi, N)

        hpi = H[pi_r][pi_c]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi_r][pi_c] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi_r, pi_c, hpi))
        while dq:
            r, c, h = dq.popleft()
            for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
                if H[nr][nc] > h:
                    H[nr][nc] = h
                    dq.append((nr, nc, h + S[nr][nc]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def build_cost_table(n):
    ret = [-1] * (n ** 2)
    for r in range(n):
        dr = min(r, n - 1 - r)
        for c in range(n):
            dc = min(c, n - 1 - c)
            ret[r * n + c] = min(dr, dc)
    return ret


def main():
    from collections import deque

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = build_cost_table(N)  # 離席コスト
    S = [1] * (N ** 2)  # 着席

    ans = 0
    for pi in p:
        hpi = H[pi]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi, hpi))
        while dq:
            x, h = dq.popleft()
            r, c = divmod(x, N)

            nx = x - N
            if r != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + N
            if r != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x - 1
            if c != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + 1
            if c != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

    print(ans)


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

import sys
def input(): return sys.stdin.readline().rstrip()

def is_integer_num(n):
    if isinstance(n, int):
        return True
    if isinstance(n, float):
        return n.is_integer()
    return False

def main():
    X = int(input())
    ROOT = 1/5
    for a in range(10000000):
        a5 = a ** 5
        b = a5 - X
        b_root = abs(b)**ROOT
        if not is_integer_num(b_root):
            continue
        if b < 0:
            if a5 + b_root ** 5 == X:
                print(a, -int(b_root))
                exit()
        else:
            if a5 - b_root ** 5 == X:
                print(a, int(b_root))
                exit()

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    X = int(input())
    for a in range(-120, 120):
        a5 = a ** 5
        for b in range(-120, 120):
            if a5 - b ** 5 == X:
                print(a, b)
                exit()

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

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

### FIXED CODE ###

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

cnt1=b//x
cnt2=(a-1)//x
print(cnt1-cnt2)
### BUGGY CODE ###

scnum = int(input())
score = ['0']*scnum
answer = 0
for i in range(scnum):
    word = input()
    if word not in score:
        score[i] = word
        answer += 1

print(answer)

### FIXED CODE ###

scnum = int(input())
word = [0]*scnum
for i in range(scnum):
    word[i] = input()
word.sort()
answer = 1

for j in range(scnum-1):
    if word[j] != word[j+1]:
        answer += 1
print(answer)