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

import sys
from heapq import heappush, heappop
from collections import defaultdict

N=input()
nl=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y,=heappop( hq )
	nl[x][y]=cost
	nl[y][x]=cost
	ans+=cost

def dij(start,end):
	d=defaultdict(lambda: float("inf")) 
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten

	while q:
		fro=heappop(q)
		for to in range(1,N+1):
			if nl[fro][to]==float("inf"): continue
			alt=d[fro]+nl[fro][to]
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]


while hq:
	cost,x,y=heappop( hq )
	d=dij(x,y)

	if d<cost:
		print -1
		quit()
	elif cost<d:
		ans+=cost
	nl[x][y]=cost
	nl[y][x]=cost


print ans


### FIXED CODE ###

import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


result = 0
for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
	#print i,j,A[i], A[j], np.min(A[i]+A[j]),d1
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print(-1)
                exit()
        else:
            result += d1
print(result)
### BUGGY CODE ###

n, k = map(int, input().split())
*a, = map(int, input().split())
d = {}
for i in a:
    d[i] = d.get(i, 0)+1
a.sort(key=lambda x: d[x])
b = sorted(set(a), key=a.index)
cnt = len(b)
ans = 0
for i in b:
    if cnt <= k:
        break
    ans += a.count(i)
    cnt -= 1
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
*a, = map(int, input().split())
d = {}
for i in a:
    d[i] = d.get(i, 0)+1
cnt = len(d)
ans = 0
for _, i in sorted(d.items(), key=lambda x: x[1]):
    if cnt <= k:
        break
    ans += i
    cnt -= 1
print(ans)
### BUGGY CODE ###

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

r = []
g = []
b = []
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif(s[i]=="G"):
        g.append(i)
    elif(s[i]=="B"):
        b.append(i)

score = len(r)*len(g)*len(b)
for i in r:
    for j in g:
        dist=abs(j-i)
        if (i>j):
            bi = i+dist
            if bi in b:
                score -=1
            bi = j-dist
            if bi in b:
                score -=1
        else:
            bi = j+dist
            if bi in b:
                score-=1
            bi = i-dist
            if bi in b:
                score-=1
        if((i+j)%2==0 and (i+j)/2 in b):
            score-=1
# print(count_)
print(score)

### FIXED CODE ###

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

r=set()
g=set()
b=set()
for i in range(n):
    if s[i]=='R':
        r.add(i)
    if s[i]=='G':
        g.add(i)
    if s[i]=='B':
        b.add(i)
score = len(r)*len(g)*len(b)
for i in r:
    for j in g:
        dist=abs(j-i)
        if (i>j):
            bi = i+dist
            if bi in b:
                score -=1
            bi = j-dist
            if bi in b:
                score -=1
        else:
            bi = j+dist
            if bi in b:
                score-=1
            bi = i-dist
            if bi in b:
                score-=1
        if((i+j)%2==0 and (i+j)/2 in b):
            score-=1
# print(count_)
print(score)
### BUGGY CODE ###

N = int(input())
#A = [0]
B = list(map(int, input().split()))
#A += B
#print(A)

sig = [0] * N

for i in range(N-1):
  print(B.count(i+1))
print(0)

#print(sig)
#for i in sig:
#  print(i)

### FIXED CODE ###

N = int(input())
A = [0]
B = list(map(int, input().split()))
A += B
#print(A)

sig = [0] * N

for i in range(N-1):
  sig[A[i+1]-1] += 1
#print(sig)

#print(sig)
for i in sig:
  print(i)
### BUGGY CODE ###

# author:  Taichicchi
# created: 17.09.2020 23:46:19


N = int(input())

S = input()

cnt = 0

for i in map(lambda x: str(x).zfill(3), range(1000)):
    f = 0
    for s in S:
        if s == i[f]:
            f += 1
        if f == 3:
            break
    if f == 3:
        cnt += 1

print(cnt)


### FIXED CODE ###

# author:  Taichicchi
# created: 17.09.2020 23:46:19


N = int(input())

S = input()

cnt = 0

for i in map(lambda x: str(x).zfill(3), range(1000)):
    f = 0
    for s in S:
        if s == i[f]:
            f += 1
        if f == 3:
            break
    if f == 3:
        cnt += 1

print(cnt)
### BUGGY CODE ###

from collections import Counter
N = int(input())
#L = []
L = [input() for _ in range(N)]
#for n in range(N):
    #S = input()
    #L.append(S)
Dic = Counter(L)
max_k_list = [kv[0] for kv in Dic.items() if kv[1] == max(Dic.values())]
max_k_list = sorted(max_k_list)
for t in max_k_list:
    print(t)

### FIXED CODE ###

from collections import Counter
N = int(input())
L = [input() for _ in range(N)]
#for n in range(N):
    #S = input()
    #L.append(S)
Dic = Counter(L)
max_value = max(Dic.values())
max_k_list = [i for i, j in Dic.items() if j == max_value]
max_k_list = sorted(max_k_list)
for t in max_k_list:
    print(t)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    a.sort()

    for i in range(m):
        a[-1] = a[-1]//2
        a.sort()

    print(sum(a))

main()


### FIXED CODE ###

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

import numpy as np

def main():
    n, m = map(int, input().split())
    a = np.array([int(i) for i in input().split()])
    a.sort()

    while True:
        temp = a[-1]//2
        a[-1] //= 2
        a.sort()
        ind = np.where(a==temp)[0][0]
        m -= 1
        if m == 0:
            print(np.sum(a))
            break
        elif n - ind < m:
            a[ind:] = a[ind:]//2
            a.sort()
            m = m - (n-ind)
        else:
            a[-m:] = a[-m:]//2
            print(np.sum(a))
            break

main()
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))

def ch_2(n):
	return n*(n-1)/2


for i in range(N):
	an = A[i]
	count=Counter(A)
	count[an]-=1
	ans=0
	for j in count.items():
		ans+=ch_2(j[1])
	print(int(ans))






### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))

def ch_2(n):
	# print(n)
	return n*(n-1)/2

count=Counter(A)

ans=0
for i in count.values():
	ans+=ch_2(i)

for j in range(N):
	ttl=ans
	ttl-=ch_2(count[A[j]])
	ttl+=ch_2(count[A[j]]-1)
	print(int(ttl))
### BUGGY CODE ###

s = input()
K = int(input())

substringList = []
for i in range(len(s)):
    for j in range(i, len(s)):
        #print(i,j)
        if(s[i:j+1] in substringList):
            pass
        else:
            substringList.append(s[i:j+1])
#substringList = list(set(substringList))
print(sorted(substringList)[K-1])


### FIXED CODE ###

s = input()
K = int(input())

substringList = []
if(len(s) < 50):
    for i in range(len(s)):
            for j in range(i, len(s)):
                #print(i,j)
                if(s[i:j+1] in substringList):
                    pass
                else:
                    substringList.append(s[i:j+1])
else:
    for i in range(len(s)):
            for j in range(i, i+5):
                substringList.append(s[i:j+1])
#substringList = list(set(substringList))
print(sorted(list(set(substringList)))[K-1])
### BUGGY CODE ###

def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

x,y,z,k = MAP()
a = MAP()
b = MAP()
c = MAP()

a.sort()
b.sort()

l = []
for i in a:
    for j in b:
        l.append(i+j)

l.sort()
c.sort()
l2 = []
for i in l[-k:]:
    for j in c[-k:]:
        l2.append(i+j)

l2.sort(reverse = True)
for i in l2[:k]:
    print(i)

### FIXED CODE ###

def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

x,y,z,k = MAP()
a = MAP()
b = MAP()
c = MAP()

a.sort()
b.sort()

l = []
for i in a:
    for j in b:
        l.append(i+j)

l.sort()
c.sort()
l2 = []
for i in l[-k:]:
    for j in c[-k:]:
        l2.append(i+j)

l2.sort(reverse = True)
for i in l2[:k]:
    print(i)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
A = [0]
for i in range(n):
  A.append(A[-1]+a[i])

ans = A[1:].count(0)
for i in range(1, n-1):
  for j in range(i+1, n):
    if A[i]-A[i-1] + A[j]-A[i] == 0: ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
A = [0]
for i in range(n):
  A.append(A[-1]+a[i])
A = Counter(A)
ans = 0
for x,y in A.items():
  if y >= 2: ans += (y-1)*y//2
print(ans)
### BUGGY CODE ###

def main():
    import numpy as np
    n = int(input())
    a = list(map(int, input().split()))
    l1 = np.zeros(61, dtype=np.int64)
    mod = 10**9+7
    powlist = np.array([pow(2, i, mod) for i in range(61)], dtype=np.int64)
    for i in a:
        cnt = 0
        k = 1
        while k <= i:
            if i & k == k:
                l1[cnt] += 1
            cnt += 1
            k *= 2
    l0 = n-l1
    ans = 0
    for i in range(len(l1)):
        ans = (ans+l0[i]*l1[i]*pow(2, i, mod)) % mod
    print(ans)


main()

### FIXED CODE ###

def main():
    n=int(input())
    a=list(map(int,input().split()))
    l1=[0]*61
    for i in a:
        j=list(reversed(bin(i)[2:]))
        for k in range(len(j)):
            if j[k]=="1":
                l1[k]+=1
    l0=[n-i for i in l1]
    ans=0
    mod=10**9+7
    for i in range(len(l1)):
        ans=(ans+l0[i]*l1[i]*pow(2,i,mod))%mod
    print(ans)
main()
### BUGGY CODE ###

from collections import defaultdict
N=int(input())

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

P=1000000007

z=0
bm=defaultdict(lambda:0)

for i in range(0,N-1):
    for j in range(i+1,N):
        if(0!=bm[(A[i],A[j])]):
            p=bm[(A[i],A[j])]
        else:
            p=A[i]*A[j]
            bm[(A[i],A[j])]=p
#        print(i,j,p)
        z+=p

z%=P
print(z)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
s=sum(A)
ss=s
z=0
for i in range(0,N-1):
    ss-=A[i]
    z+=A[i]*ss

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

rules = ['dream', 'dreamer', 'erase', 'eraser']

s = input()
stack = [0]
mem = [0]
ok = False
loop = 0
while len(stack) > 0:
    loop += 1
    #print(stack, mem)
    start_id = stack.pop()
    string = s[start_id:]
    if start_id == len(s):
        print('YES')
        ok = True
        break

    for rule in rules:
        if string.startswith(rule):
            next_start_id = start_id + len(rule)
            if next_start_id <= len(s):
                part = string[next_start_id:]
                #if part.startswith('d') or part.startswith('e') or part == '':
                if next_start_id not in mem:
                    stack.append(next_start_id)
                    mem.append(next_start_id)
if not ok:
    print('NO')

### FIXED CODE ###

rules = ['dream', 'dreamer', 'erase', 'eraser']

s = input()
stack = [0]
mem = [0 for _ in range(len(s)+1)]
ok = False
while len(stack) > 0:
    start_id = stack.pop()
    string = s[start_id:]
    if start_id == len(s):
        print('YES')
        ok = True
        break

    for rule in rules:
        if string.startswith(rule):
            next_start_id = start_id + len(rule)
            if next_start_id <= len(s):
                part = string[next_start_id:]
                if mem[next_start_id] == 0:
                    stack.append(next_start_id)
                    mem[next_start_id] = 1
if not ok:
    print('NO')
### BUGGY CODE ###

n = int(input())
print(sum(range(1,n)))

### FIXED CODE ###

n=int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

from operator import mul
from functools import reduce

n, a, b = map(int, input().split())

def combinations_count(n, r):
  if n < r:
    return 0
  r = min(r, n - r)
  numer = reduce(mul, range(n, n - r, -1), 1)
  denom = reduce(mul, range(1, r + 1), 1)
  return numer // denom

print((2**n - 1 - combinations_count(n, a) - combinations_count(n, b)) % (10 ** 9 + 7))


### FIXED CODE ###

from operator import mul
from functools import reduce

n, a, b = map(int, input().split())

mod = 10 ** 9 + 7

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     :
      return 1
    elif y == 1     :
      return x % mod
    elif y % 2 == 0 :
      return power(x, y//2)**2 % mod
    else            :
      return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

r1 = min(a, n - a)
r2 = min(b, n - b)

if r1 > r2:
  r1, r2 = r2, r1

numer1 = reduce(mul, range(n, n - r1, -1), 1)
denom1 = reduce(mul, range(1, r1 + 1), 1)
numer2 = reduce(mul, range(n - r1, n - r2, -1), numer1)
denom2 = reduce(mul, range(r1 + 1, r2 + 1), denom1)

print((power(2, n) - 1 - div(numer1, denom1) - div(numer2, denom2)) % (10 ** 9 + 7))
### BUGGY CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
n = int(readline())
a = list(map(int, readline().split()))
b = defaultdict(list)
c = defaultdict(list)

for i, v in enumerate(a, 1):
  b[i + v].append(i)
  c[i - v].append(i)
c = dict(c)

ans = 0
for v, L in b.items():
  for i in L:
    if v in c:
      for j in c[v]:
        if i < j:
          ans += 1
print(ans)

### FIXED CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
n = int(readline())
a = list(map(int, readline().split()))
b = defaultdict(list)
c = defaultdict(list)

for i, v in enumerate(a, 1):
  b[i + v].append(i)
  if 2 <= i - v <= 100000001:
    c[i - v].append(i)
c = dict(c)

ans = 0
for v, L in b.items():
  for j in L:
    if v in c:
      ans += len(c[v])
print(ans)
### BUGGY CODE ###

N = int(input())
a = (list(map(int, input().split())))
for i in range(N):
    a.append(a[i] - 1)
    a.append(a[i] + 1)
a.sort()
X = 1
for x in range(a[0], a[-1]):
    X = max(X, a.count(x))
print(X)

### FIXED CODE ###

import collections
N = int(input())
a = (list(map(int, input().split())))
for i in range(N):
    a.append(a[i] - 1)
    a.append(a[i] + 1)
c = collections.Counter(a)
print(c.most_common()[0][1])
### BUGGY CODE ###

a,b,n = list(map(int, input().split()))
fnc = lambda x: int(a*x/b) - a*int(x/b)
prev = 0
for i in range(n+1):
    now = fnc(i)
    if prev > now:
        print(prev)
        break
    elif i == n:
        print(now)
        break
    prev = now

### FIXED CODE ###

a,b,n = list(map(int, input().split()))
if n < b:
    print(int(a/b * n))
else:
    print(int(a/b * (b-1)))
### BUGGY CODE ###

n = int(input())
nums = list(map(int, input().split()))
cnt = 1
for i in range(n - 1):
    if nums[i + 1] < min(nums[:i + 1]):
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
cnt = 1
min = nums[0]
for i in range(1, n):
    if nums[i] < min:
        min = nums[i]
        cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
s,t = map(int,input().split())
visited = [[-1,-1,-1] for i in range(n+1)]
que = deque([(s,0,0)])
while que:
  x,mod,cnt = que.popleft()
  visited[x][mod] = cnt
  if x == t and mod == 0:
    break
  for y in graph[x]:
    if visited[y][(mod+1)%3] == -1:
      que.append((y,(mod+1)%3,cnt+1))
      visited[y][(mod+1)%3] == cnt+1
print(visited[t][0]//3)

### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
s,t = map(int,input().split())
visited = [[-1,-1,-1] for i in range(n+1)]
que = deque([(s,0,0)])
while que:
  x,mod,cnt = que.popleft()
  visited[x][mod] = cnt
  if x == t and mod == 0:
    break
  for y in graph[x]:
    if visited[y][(mod+1)%3] == -1:
      que.append((y,(mod+1)%3,cnt+1))
      visited[y][(mod+1)%3] = cnt+1
print(visited[t][0]//3)
### BUGGY CODE ###

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

answer = s.count('R') * s.count('G') * s.count('B')

for i in range(n - 2):
  j = 0
  while((i + 1) + (j - i) * 2 <= n):
    if s[i] != s[j] and s[j] != s[(i + 1) + (j - i) * 2] and s[i] != s[(i + 1) + (j - i) * 2]:
      answer -= 1
      j += 1

print(answer)

### FIXED CODE ###

n = int(input())
s = input()
 
answer = s.count('R') * s.count('G') * s.count('B')

for i in range(n - 2):
  j = i + 1
  while((i + 1) + (j - i) * 2 <= n):
    if s[i] != s[j] and s[j] != s[i + (j - i) * 2] and s[i] != s[i + (j - i) * 2]:
      answer -= 1
    j += 1
 
print(answer)
### BUGGY CODE ###

import numpy as np


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def reset(self):
        self.tree = [0] * (self.size + 1)


def solve(n, aaa):
    t = n * (n + 1) // 4
    alt = sorted(set(aaa))
    l, r = 0, len(alt) - 1
    bt = Bit(n * 2)
    while l <= r:
        m = (l + r) // 2
        ccc = ((((aaa - alt[m]) >= 0) * 2 - 1).cumsum() + n).tolist()
        bt.add(n, 1)
        right_order = 0
        for p in ccc:
            right_order += bt.sum(p)
            bt.add(p, 1)
        if right_order >= t:
            l = m + 1
        else:
            r = m - 1
        bt.reset()
    return alt[r]


n = int(input())
aaa = np.array(list(map(int, input().split())))
print(solve(n, aaa))


### FIXED CODE ###

from itertools import accumulate


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def reset(self):
        self.tree = [0] * (self.size + 1)


def solve(n, aaa):
    t = n * (n + 1) // 4
    alt = sorted(set(aaa))
    l, r = 0, len(alt) - 1
    bt = Bit(n * 2)
    while l <= r:
        m = (l + r) // 2
        am = alt[m]
        ccc = accumulate(1 if a - am >= 0 else -1 for a in aaa)
        bt.add(n, 1)
        right_order = 0
        for p in ccc:
            p += n
            right_order += bt.sum(p)
            bt.add(p, 1)
        if right_order >= t:
            l = m + 1
        else:
            r = m - 1
        bt.reset()
    return alt[r]


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect

def main():
    n=int(input())
    l=sorted(list(map(int,input().split())))
    ans=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            ans+=bisect.bisect_left(l[j+1:],l[i]+l[j])
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left

def main():
    n=int(input())
    l=sorted(list(map(int,input().split())))
    ans=0
    for i in range(n-2):
        a=l[i]
        for j in range(i+1,n-1):
            ans+=bisect_left(l,a+l[j])-j-1
    print(ans)

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

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

mod = 10**9+7
ans = 0

for k in range(60):
    x = 0
    y = 0
    for a in A:
        if a & 1<<k:
            x += 1
        else:
            y += 1
    ans += x*y*pow(2, k, mod)
    ans %= mod
print(ans)

### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))

    mod = 10**9+7
    ans = 0

    for k in range(60):
        x, y = 0, 0
        for a in A:
            x += 1 & a>>k
        tmp = x*(n-x)%mod
        tmp *= pow(2, k, mod)
        ans += tmp
        ans %= mod
    print(ans)


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

from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX*2+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(A,B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (A,B),v in goals.iteritems():
		ans = (ans+(dp[Base+B][Base+A]-F[A*2+B*2]*Finv[A*2]*Finv[B*2]%p)*v) % p
	print (ans + p)*pow(2,p-2,p) % p
solve()

### FIXED CODE ###

from collections import defaultdict
def solve():
	Base = 2000
	MAX = Base*2
	p = 10**9+7
	F = [1]; Finv = [0]*(MAX*2+1)
	for i in xrange(MAX*2): F.append(F[i]*(i+1)%p)
	Finv[MAX] = pow(F[MAX],p-2,p)
	for i in xrange(MAX,0,-1): Finv[i-1] = Finv[i]*i%p
	N = int(raw_input())
	dup = A_MAX = B_MAX = 0
	dp = [[0]*(MAX+2) for i in xrange(MAX+2)]
	goals = defaultdict(int)
	for i in xrange(N):
		A,B = map(int,raw_input().split())
		dup = (dup + F[A*2+B*2]*Finv[A*2]*Finv[B*2])%p
		if A > A_MAX: A_MAX = A
		if B > B_MAX: B_MAX = B
		goals[(Base+A,Base+B)] += 1
		dp[Base-B][Base-A] += 1
	for j in xrange(Base-B_MAX,Base+B_MAX+1):
		for i in xrange(Base-A_MAX,Base+A_MAX+1):
			dp[j+1][i] = (dp[j+1][i] + dp[j][i]) % p
			dp[j][i+1] = (dp[j][i+1] + dp[j][i]) % p
	ans = 0
	for (i,j),v in goals.iteritems():
		ans = (ans + dp[j][i]*v) % p
	print ((ans - dup)*pow(2,p-2,p)+p) % p
solve()
### BUGGY CODE ###

N = int(input())
S = input()

def z_algo2(S):
    N = len(S)
    A = [0]*N 
    A[0] = N 
    j = 1 
    i = 1 
    for i in range(N):
        c = j + A[j] - i
        if c <= 0:
            k = 0
            while i + k < N and S[k] == S[i + k]:
                k += 1
            A[i] = k
            j = i
        elif c > 0:
            if A[i - j] == c:
                k = 0
                while i + k + c < N and S[c + k] == S[i + c + k]:
                    k += 1
                A[i] = c + k
                j = i
            elif A[i - j] > c:
                A[i] = c
                j = i
            else:
                A[i] = A[i - j]
    for i in range(N):
        A[i] = min(i, A[i])
    return A

print(max([max(z_algo2(S[i:])[1:]) for i in range(N - 1)]))

### FIXED CODE ###

N = int(input())
S = input()
r = 1
ans = 0
for i in range(N):
    while True:
        if S.rfind(S[i : r + 1]) >= r + 1:
            r += 1
            ans = max(ans, r - i)
        else:
            break
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter


def input():
    return sys.stdin.readline().strip()
# sys.setrecursionlimit(100000)


def helper(cur: list, B, candi, ans, rest):
    if rest == 0:
        if cur == B:
            for i in ans:
                print(i)
            sys.exit()
        else:
            return
    for k, v in candi.items():
        if v > 0 and len(cur) + 1 >= k:
            cur.insert(k - 1, k)

            candi[k] -= 1
            helper(cur, B, candi, ans + [k], rest - 1)
            cur.pop(k - 1)
            candi[k] += 1


def main():
    n = int(input().strip())
    B = [int(i) for i in input().strip().split()]
    counter = Counter(B)
    helper([], B, counter, [], n)
    print(-1)
    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()
# sys.setrecursionlimit(100000)


def main():
    n = int(input().strip())
    B = [int(i) for i in input().strip().split()]
    ans = []
    ptr = len(B)
    while ptr > 0:
        if B[ptr - 1] == ptr:
            ans.append(B.pop(ptr - 1))
            ptr = len(B)
        else:
            ptr -= 1
    if len(ans) == n:
        for i in ans[::-1]:
            print(i)
    else:
        print(-1)

    return


if __name__ == "__main__":
    main()