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

import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
sys.setrecursionlimit(1000000)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**18]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0

while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
                    


print(-1)
    




### FIXED CODE ###

import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)
### BUGGY CODE ###

n=int(input())
lb,ub=0,len(str(n))
while ub-lb>1:
	mid=(lb+ub)//2
	if sum(map(int,str(9*n+9*mid)))<=9*mid:
		ub=mid
	else:
		lb=mid
print(ub)

### FIXED CODE ###

n=list(input())
n.reverse()
lb,ub=0,len(n)
def check(x):
	g=0
	for i in n:
		x-=(x+g-int(i))%10
		if x<0:
			break
		g=(x+g)//10
	return x>=0
while ub-lb>1:
	mid=(lb+ub)//2
	if check(9*mid):
		ub=mid
	else:
		lb=mid
print(ub)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

import numpy as np
from numba import njit

N = int(input())
scores = np.array([int(i) for i in input().split()], dtype='int64')
dpt = np.full((N, N), -10**18, dtype='int64')

#@njit('i8(i8[:],i8[:,:],i8,i8)', cache=True)
def get_max_score(scores, dpt, i, j):
    if i == j:
        dpt[i][j] = scores[i]
        return scores[i]
    else:
        if dpt[i][j] != -10**18:
            return dpt[i][j]
        result = max(scores[i] - get_max_score(scores, dpt, i+1, j), scores[j] - get_max_score(scores, dpt, i, j-1))
        dpt[i][j] = result
        return result

print(get_max_score(scores, dpt, 0, len(scores)-1))


### FIXED CODE ###

import numpy as np
from numba import njit

N = int(input())
scores = np.array(list(map(int, input().split())), dtype='int64')
dpt = np.full((N, N), -10**18, dtype='int64')

@njit('i8(i8[:],i8[:,:],i8,i8)', cache=True)
def get_max_score(scores, dpt, i, j):
    if i == j:
        dpt[i][j] = scores[i]
        return scores[i]
    else:
        if dpt[i][j] != -10**18:
            return dpt[i][j]
        result = max(scores[i] - get_max_score(scores, dpt, i+1, j), scores[j] - get_max_score(scores, dpt, i, j-1))
        dpt[i][j] = result
        return result

print(get_max_score(scores, dpt, 0, len(scores)-1))
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(5)]
ninzu = [n,0,0,0,0,0]
count = 0
while True:
    if ninzu[5] == n:
        break
    count += 1
    for i,number in enumerate(a[::-1]):
        i = 4-i
        if number>=ninzu[i]:
            ninzu[i+1] += ninzu[i]
            ninzu[i] = 0
        else:
            ninzu[i+1] += number
            ninzu[i] -= number
print(count)


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(5)]
min_a = min(a)
ans = 4
ans += n//min_a
if n%min_a != 0:
    ans += 1
print(ans)
### BUGGY CODE ###

s=input()
n=int(input())
for i in range(n):
    q=input().split()
    if(len(q)==1):
        s=s[::-1]
        continue
    if(int(q[1])==1):s=q[2]+s
    if(int(q[1])==2):s=s+q[2]
print(s)

### FIXED CODE ###

s=input()
n=int(input())
t=True
a=str()
b=str()
for i in range(n):
    q=input().split()
    if(len(q)==1):
        t=not t
        continue
    if(int(q[1])==1):
        if(t):a=q[2]+a
        else:b=b+q[2]
    if(int(q[1])==2):
        if(t):b=b+q[2]
        else:a=q[2]+a
if(t):print(a+s+b)
else:print(b[::-1]+s[::-1]+a[::-1])
### BUGGY CODE ###

k = int(input())
lis = []
num = 0
i = 0
while num < k:
    i += 1
    a = list(map(int, list(str(i))))
    j = 0
    tf = True
    while j < len(a)-1:
        if abs(a[j]-a[j+1]) > 1:
            tf = False
            break
        j += 1
    if tf == True:
        num += 1
print(i)

### FIXED CODE ###

k = int(input())
lis = [1,2,3,4,5,6,7,8,9]
i=0
while len(lis) < k:
	m = lis[i]%10
	if m != 0:
		lis.append(int(str(lis[i])+str(m-1)))
	lis.append(int(str(lis[i])+str(m)))
	if m!= 9:
		lis.append(int(str(lis[i])+str(m+1)))
	i+=1
print(lis[k-1])
### BUGGY CODE ###

from itertools import combinations

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

count = 0
for bars in list(combinations(L, 3)):
    if bars[2] < bars[0] + bars[1]:
        if bars[1] - bars[0] < bars[2]:
            count += 1

print(count)

### FIXED CODE ###

N = int(input())
L = sorted(list(map(int, input().split())), reverse=True)

def aaa(arr): 
    n = len(arr) 
    arr.sort() 
    count = 0
    for i in range(0,n-2): 
        k = i + 2
        for j in range(i+1,n): 
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
            if(k>j): 
                count += k - j - 1
  
    return count 

print(aaa(L))
### BUGGY CODE ###

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

x=0
list =[]
while  0<= x <= n :
    k = int(a*x/b) - a* int(x/b)
    list.append(k)
    x += 1
print(max(list))

### FIXED CODE ###

a,b,n = map(int, input().split())
x = min(b-1,n)
print(int(a*x/b))
### BUGGY CODE ###

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

h = int(m/n)+1
x = 0
for a in range(h, 0, -1):
    q = m-a*n
    if q>=0 and m%a == 0:
        print(a)
        break

### FIXED CODE ###

import sys

def make_divisors(num):
    divisors = []
    for i in range(1, int(num**0.5)+1):
        if num%i == 0:
            divisors.append(i)
            if num//i != i:
                divisors.append(num//i)
    divisors.sort()
    return divisors

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

divisors = make_divisors(m)

for i in range(1, len(divisors)+1):
    if divisors[i*-1] * n <= m:
        print(divisors[i*-1])
        sys.exit()
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
ans=1
for i in range(K):
  ans*=A[i]
for i in range(K,N):
  bns=ans//A[i-K]*A[i]
  if ans<bns:
    print('Yes')
  else:
    print('No')
  ans=bns

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(K,N):
  if A[i-K]<A[i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

n=int(input())
a = list(map(int,input().split()))
def p(val):
    print(val)

sho = 10**9 +7
count = 0
for i in range(n-1):
    for j in range(i+1,n):
        count += ((a[i]%sho)*(a[j]%sho)) % sho
        if count > sho:
            count = count%sho
p(count)

### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
def p(val):
    print(val)
 
sho = 10**9 +7
a1 = sum(a)**2
b1 = list(map(lambda y:y**2,a))
b2=sum(b1)
result = ((a1-b2)//2)% sho
p(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n, q = map(int, input().split())
s = input()

s_idx = {}
for i, c in enumerate(s):
    if c in s_idx:
        s_idx[c].append(i)
    else:
        s_idx[c] = [i]

golem_pos = [1 for _ in range(n)]
for _ in range(q):
    t, d = input().split()

    step = 1 if d == 'L' else -1

    if t not in s_idx:
        continue

    for i in s_idx[t][::step]:
        if i == 0 and d == 'L':
            golem_pos[i] = 0
        elif i == n-1 and d == 'R':
            golem_pos[i] = 0
        elif d == 'L':
            golem_pos[i-1] += golem_pos[i]
            golem_pos[i] = 0
        else:
            golem_pos[i+1] += golem_pos[i]
            golem_pos[i] = 0

print(sum(golem_pos))


### FIXED CODE ###

# -*- coding: utf-8 -*-
def vanish_golem(pos, n, s, spells):
    for t, d in spells:
        if pos < 0:
            return -1
        if pos >= n:
            return 1

        if s[pos] == t:
            pos += 1 if d == 'R' else -1

    if pos < 0:
        return -1
    elif pos >= n:
        return 1
    else:
        return 0


def search_vanish_golem(n, s, spells, th):
    l = 0
    h = n-1

    while l <= h:
        t = l + (h - l) // 2
        v = vanish_golem(t, n, s, spells)
        if v < th:
            l = t + 1
        else:
            h = t - 1

    return l


n, q = map(int, input().split())
s = input()

td = [input().split() for _ in range(q)]

l_cnt = search_vanish_golem(n, s, td, 0)
r_cnt = n - search_vanish_golem(n, s, td, 1)

print(n - l_cnt - r_cnt)
### BUGGY CODE ###

n = int(input())
print(sum(i for i in range(1,n)))



### FIXED CODE ###

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

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

ret = 0
for i in range(0, len(A)-1):
  for j in range(i+1, len(A)):
    ret += A[i]*A[j]

modn = int(1e9 + 7)
print(ret % modn)

### FIXED CODE ###

import numpy as np

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

modn = int(1e9 + 7)

ruiseki = sum(A)

ret = 0
for i in range(0, len(A)-1):
  ruiseki -= A[i]
  ret += A[i] * ruiseki

print(np.mod(ret, modn))
### BUGGY CODE ###

N, a, b = map(int, input().split())
x = (N//(a+b)) *a
l=[]
for i in range(a):
  l.append('b')
for i in range(b):
  l.append('r')
y = l[0:int(N%(a+b))]
print(x + y.count('b'))

### FIXED CODE ###

N, a, b =map(int, input().split())
count=N//(a+b)
ans= count * a + min(N % (a + b), a)
print(ans)
### BUGGY CODE ###

from itertools import accumulate as ac
from functools import reduce

n,k=map(int,input().split())
*ac,=ac([0]+list(map(int,input().split())))
count_bits=lambda n:sum(map(lambda x:x&n==n,l))

l=[]
for i in range(n+1):
    for j in range(i+1,n+1):
        l.append(ac[j]-ac[i])

ans=0
for i in range(41)[::-1]:
    if count_bits(ans|1<<i)>=k:
        ans|=1<<i

print(ans)

### FIXED CODE ###

from itertools import accumulate as ac

n,k=map(int,input().split())
*a,=ac([0]+list(map(int,input().split())))

l=[a[j]-a[i] for i in range(n+1) for j in range(i+1,n+1)]
f=lambda n:sum(map(lambda x:x&n==n,l))

ans=0
for i in range(41)[::-1]:
    if f(ans|1<<i)>=k:
        ans|=1<<i

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

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

B = []

if N % 2 == 0:
    for i in range(N):
        if i % 2 == 0:
            B.append(A[i])
        else:
            B.insert(0,A[i])
else:
    for i in range(N):
        if i % 2 == 0:
            B.insert(0,A[i])
        else:
            B.append(A[i])

print(*B)



### FIXED CODE ###

from collections import deque

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

B = deque(maxlen=2*10**5)

if N % 2 == 0:
    for i in range(N):
        if i % 2 == 0:
            B.append(A[i])
        else:
            B.appendleft(A[i])
else:
    for i in range(N):
        if i % 2 == 0:
            B.appendleft(A[i])
        else:
            B.append(A[i])

print(*B)
### 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 = [a + b for a in A for b in B]
AB.sort()
AB = AB[-K:]

ans = [ab + c for ab in AB for c in C]
ans.sort()

for x in ans[-K:][::-1]:
    print(x)


### FIXED 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 = [a + b for a in A for b in B]
AB.sort()
AB = AB[-K:]

ans = [ab + c for ab in AB for c in C]
ans.sort()

for x in ans[-K:][::-1]:
    print(x)
### BUGGY CODE ###

def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

from math import sqrt

N = INT()
tmp = N
fact = {}
is_prime = True

for n in range(2, int(sqrt(N)) + 1):
    if tmp == 1:
        break
    
    e = 0
    while 1:
        if tmp % n != 0:
            break
        tmp //= n
        e += 1
    
    if e == 0:
        continue

    fact[n] = e

if tmp != 1:
    
    fact[tmp] = 1

if fact == {}:
    fact[N] = 1

ans = 0

for p in fact.keys():
    e = 1
    z = p**e
    
    while 1:
        if N % z != 0:
            break
        N //= z
        e += 1
        z = pow(p, e)
        ans += 1
        
    if N == 1:
        break

print(ans)

### FIXED CODE ###

from collections import Counter
import math

def div(n):
    prime = []
    tmp = int(math.sqrt(n)) + 1
    
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            prime.append(num)
    
    if n != 1:
        prime.append(n)
    return prime

n = int(input())
prime_div = Counter(div(n))
ans = 0

for p, ex in prime_div.items():
    k = 1
    while ex >= k:
        ex -= k
        ans += 1
        k += 1

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

import fractions
import numpy

from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    sa = set(a)

    lcm = 1

    for ai in sa:
        lcm = (ai * lcm) // fractions.gcd(ai, lcm)

    ans = 0

    ans = numpy.sum([lcm // ai for ai in a])

    ans %= 10 ** 9 + 7

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import fractions

from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    sa = set(a)

    lcm = 1

    for ai in sa:
        lcm = (ai * lcm) // fractions.gcd(ai, lcm)

    ans = 0

    for ai in a:
        ans += lcm // ai
    ans %= 10 ** 9 + 7

    print(ans)


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

# coding: utf-8
s = input()
k = int(input())
sb_str = []
for i in range(len(s)+1):
    for j in range(1,len(s)+1):
        if i < j:
            sb_str.append(s[i:j])

sb_str = list(set(sb_str))
sb_str.sort()
print(sb_str[k-1])


### FIXED CODE ###

# coding: utf-8
s = input()
k = int(input())
sb_str = []
for i in range(len(s)+1):
    for j in range(1+i,len(s)+1):
        if len(s[i:j]) > 5:
            break
        if i < j:
            sb_str.append(s[i:j])

sb_str = list(set(sb_str))
sb_str.sort()
print(sb_str[k-1])
### BUGGY CODE ###

n = int(input()) 
t = [int(input()) for i in range(n)] 

for j in t:
  if j != max(t):
  	print(max(t))
  else:
    print(sorted(t)[n-2])

### FIXED CODE ###

n = int(input()) 
t = [int(input()) for i in range(n)] 

ma = max(t)
ma2 = sorted(t)[n-2]

for j in t:
  if j != ma:
  	print(ma)
  else:
    print(ma2)
### BUGGY CODE ###



global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

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

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E50)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)
   

### FIXED CODE ###



global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

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

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E48)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)
### BUGGY CODE ###

import math
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res

n = readInt()
a = readInts()

li = []
ri = []

for i in range(n):
	li.append(i+a[i])
	ri.append(i-a[i])

li.sort()
ri.sort()

res = 0

while 1:
	if len(li)==0:
		break
	i = li.pop(0)
	c=1
	try:
		while 1:
			li.remove(i)
			c+=1
	except:
		pass
	finally:
		res+=ri.count(i)*c

print(res)

### FIXED CODE ###

import math
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def pop2(li):
	c=1
	i=li.pop(0)
	while 1:
		j=li.pop(0)
		if j==i:
			c+=1
		else:
			break
	return i,c,[j]+li

n = readInt()
a = readInts()

li = []
ri = []

d1 = defaultdict(int)
d2 = defaultdict(int)

for i in range(n):
	d1[i+a[i]]+=1
	d2[i-a[i]]+=1

ans = 0

for key in d1:
	ans+=d1[key]*d2[key]

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

n,m,s,t=map(int,input().split())
yen=[[]*n for i in range(n)]
sunuke=[[]*n for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u-1].append((a,v-1))
  yen[v-1].append((a,u-1))
  sunuke[u-1].append((b,v-1))
  sunuke[v-1].append((b,u-1))
  


#ダイクストラ法
#n:頂点数　s:始点　es:隣接リスト表現
import heapq
def dijkstra(n,s,es):
  d=[float("INF")]*n
  d[s]=0
  used=[False]*n
  used[s]=True
  edgelist=[]
  for to in es[s]:
    heapq.heappush(edgelist,to)
  while len(edgelist)>0:
    minedge=heapq.heappop(edgelist)
    v=minedge[1]
    if used[v]:
      continue
    used[v]=True
    d[v]=minedge[0]
    for to in es[v]:
      heapq.heappush(edgelist,(d[v]+to[0],to[1]))
  return d

ans=[0]*n
d_yen=dijkstra(n,s-1,yen)
d_sunuke=dijkstra(n,t-1,sunuke)

for i in range(n):
  ans[i]=d_yen[i]+d_sunuke[i]
  

for j in range(n):
  print(10**15-min(ans[j:]))
  
  
  
  
      
    
    
    
    
  
  


  

### FIXED CODE ###

n,m,s,t=map(int,input().split())
yen=[[]*(n+1) for i in range(n+1)]
sunuke=[[]*(n+1) for i in range(n+1)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  yen[u].append((a,v))
  yen[v].append((a,u))
  sunuke[u].append((b,v))
  sunuke[v].append((b,u))
  
import heapq
#n:頂点数、m:辺の数　s:始点　es:辺のリスト
def dijkstra(n,m,s,es):
  #used:訪問済みかどうかを確認する　false 使ってない
  used=[False]*(n+1)
  d=[float("INF")]*(n+1)
  d[s]=0
  used[s]=True
  q=[]
  for to in es[s]:
    heapq.heappush(q,to)
  while len(q)>0:
    minedge=heapq.heappop(q)
    v=minedge[1]
    if used[v]==True:
      continue
    cost=minedge[0]
    d[v]=cost
    used[v]=True
    for to in es[v]:
      heapq.heappush(q,(d[v]+to[0],to[1]))
  return d


d_yen=dijkstra(n,m,s,yen)
d_sunuke=dijkstra(n,m,t,sunuke)

ans=[float("INF")]*(n+1)
num=float("INF")
for i in range(n,0,-1):
  num=min(d_yen[i]+d_sunuke[i],num)
  ans[i]=num
  
for j in range(1,n+1):
  print(10**15-ans[j])
### BUGGY CODE ###

n=int(input())
num=list(map(int,input().split()))
don=[]
cnt=0
for i in num:
    flg=True
    for j in don:
        if i > j:
            flg=False
    if flg:
        don.append(i)
        cnt+=1
print(cnt)

### FIXED CODE ###

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

n = int(input())
s = [input() for i in range(n)]
s.sort()
l = sorted(set(s))
ms = len(s) - len(l)
if ms == 0:
    print("\n".join(s))
    exit()

ans = 0
ans_l = []
for i in l:
    sc = s.count(i)
    if sc > ans:
        ans_l = [i]
        ans = sc
    elif sc == ans:
        ans_l.append(i)
      
print("\n".join(ans_l))

### FIXED CODE ###

from collections import Counter

n = int(input())
S = [input() for i in range(n)]

s = Counter(S)
max_cnt = max(s.values())
names = [name for name, cnt in s.items() if cnt == max_cnt]
names.sort()

print("\n".join(names))
### BUGGY CODE ###

n = int(input())
ans = 0

def add(n):
    if n%2 == 0:
        return sum(range(1,n))
    else:
        p = (n // 2 ) + 1
        return (n % p) + sum(range(1,n)) - (p-1)

print(add(n))


### FIXED CODE ###

n = int(input())
ans = 0

def add(n):
    if n%2 == 0:
        return sum(range(1,n))
    else:
        p = (n // 2 ) + 1
        return (n % p) + sum(range(1,n)) - (p-1)

print(add(n))
### BUGGY CODE ###

import math
K = int(input())
total = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
           d = math.gcd(a+1,b+1)
           total += math.gcd(d,c+1)
print(total)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
total = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
           total += gcd(a+1,b+1,c+1)
print(total)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    S = input()
    amari = []
    l = len(S)
    amari =[int(S[-(i + 1) :]) % 2019 for i in range(l)]
    print(l - len(set(amari)) + amari.count(0))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    S = input()[::-1] # 入力文字列を逆順で格納
    counts = [0] * 2019
    counts[0] = 1
    num, d = 0, 1

    for char in S:
        num = num + int(char) * d
        num = num % 2019
        d = d * 10
        d = d % 2019
        counts[num] += 1 #余りの数の番号のリストに+1していくことでカウント

    ans = 0
    for cnt in counts:
        ans += cnt * (cnt - 1) // 2
    print(ans)

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

import math
K = int(input())

def gcd_plus(a,b,c):
  num_list = [a,b,c]
  N = len(num_list)
  ans = num_list[0]
  for i in range(1,N):
    ans = math.gcd(ans,num_list[i])
  return ans

sum = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      sum += gcd_plus(a,b,c)
      
print(sum)


### FIXED CODE ###

import math
K = int(input())

sum = 0
gcd_a_b = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    gcd_a_b = math.gcd(a,b)
    for c in range(1,K+1):
      sum += math.gcd(gcd_a_b,c)
      
print(sum)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
	l,r=map(int,input().split())
	print(s[l-1:r].count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()

len=len(s)
L=[0]*len
R=[0]*len
res=s.count("AC")

cnt=0
for i in range(len-1):
	if s[i]=="A" and s[i+1]=="C":
		cnt+=1
	L[i+1]=cnt

cnt=0
for i in range(len-1):
	if s[len-i-1]=="C" and s[len-i-2]=="A":
		cnt+=1
	R[len-i-2]=cnt

for _ in range(q):
	l,r=map(int,input().split())
	print(res-L[l-1]-R[r-1])