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

import collections
n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

kari = 1

for j in range(kosu):
    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)

kari_old = kari

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    #kari = 1
    #for j in range(kosu):
    #    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for j in keys:
        kari *= pow(pow(j,pri_li[i][j],mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)


### FIXED CODE ###

import collections
import math
n = int(input())
ai = [int(i) for i in input().split()]

mod = 10**9+7

if n == 1:
    print(1)
    exit()
    
    
# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor


dic = {}
for a in ai:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

kari = 1
for num,count in dic.items():
    kari *= pow(num,count,mod)
    kari %= mod

kari_old = kari
ans = 0

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    #kari = 1
    #for j in range(kosu):
    #kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    kari *= pow(ai[i],mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
    #print(ans)
        
print(ans)
### BUGGY CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 仕方ないので，numpy で同時代入
import numpy as np
import sys
H, W = list(map(int, input().split()))
all_in = sys.stdin.readlines()
all_count = H * W
blacks = np.asarray([i*W+j for i in range(H) for j in range(W) if all_in[i][j] == "#"])
L = np.asarray([False]*all_count)
L[blacks] = True
black_count = len(blacks)
 
cands_H = [-W, W]
cands_W = [-1, 1]
result = 0
while black_count < all_count:
  next_steps = set(blacks[blacks%W!=0]-1)|set(blacks[blacks%W!=W-1]+1)|set(blacks-W)|set(blacks+W)
  blacks = np.asarray([i for i in next_steps if i >= 0 and i < all_count and not L[i]])
  L[blacks] = True
  black_count += len(blacks)
  #print(blacks)
  result += 1

print(result)

### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy

def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)

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

N = int(input())
a = 1
for Ai in input().split(' '):
    a *= int(Ai)
    if a == 0:
        break

if a > 10**18:
    print('-1')
else:
    print(a)


### FIXED CODE ###

_ = int(input())
A = [ int(i) for i in input().strip().split(' ')]
a = 1
if min(A) == 0:
    print(0)
else:
    for Ai in A:
        a *= Ai
        if a > 10**18:
            print('-1')
            break
    else:
        print(a)
### BUGGY CODE ###

import itertools
N = int(input())
lst = []
cnt = 0
for i in range(N):
    s = str(input())
    lst.append(sorted(s))
ans = itertools.combinations(lst, 2)
for j in ans:
    if j[0] == j[1]:
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
dic = {}
sum = 0
for i in range(N):
    s = ''.join(sorted(str(input())))
    if s in dic:
      dic[s] += 1
    else:
      dic[s] = 1
for i in dic.values():
    if i > 1:
        sum += i*(i-1)/2
print(int(sum))
### BUGGY CODE ###

N, A, B = map(int, input().split())
round_count = 0

med = N / 2 + 0.5

while(True):
    if abs(A - B) % 2 == 0:
        if A > B:
            A = A - 1
            B = B + 1
        else:
            A = A + 1
            B = B - 1
    else:
        Max = max([A, B])
        Min = min([A, B])
        if (Max + Min) / 2 > med:
            A = A + 1
            B = B + 1
        else:
            A = A - 1
            B = B - 1

    if A < 1:
        A = 1
    elif A > N:
        A = N
    elif B < 1:
        B = 1
    elif B > N:
        B = N

    round_count = round_count + 1

    if A == B:
        break

print(round_count)

### FIXED CODE ###

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

med = N / 2 + 0.5
Sub = B - A

if (Sub) % 2 == 0:
    round_count = Sub // 2
else:
    round_count = min(A - 1, N - B) + 1 + (Sub - 1) // 2
            
print(round_count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
while len(A)>1:
    p = A[0]
    if A[0] != A[1]:
        A = [j for j in A if j % p !=0]
        ans += 1
    else:
        A = [j for j in A if j % p !=0]
if len(A)==1:
    print(ans+1)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
from collections import Counter
AA = Counter(A)
dp = [True]*(A[-1]+1)
ans = 0
for k,v in AA.items():
    if dp[k]==True and v == 1:
        ans += 1
    for i in range(A[-1]//k+1):
        dp[k*i] = False
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
checked=set()
from collections import defaultdict
branch=defaultdict(dict)
flag=True
for i in range(M):
    L,R,D=map(int,input().split())
    branch[L-1][R-1]=D
    branch[R-1][L-1]=-1*D
for i in range(N):
    if i in checked:
        continue
    dist=dict()
    dist[i]=0
    check={i}
    while len(check)>0:
        now=check.pop()
        checked|={now}
        for nex,d in branch[now].items():
            if nex not in dist.keys():
                dist[nex]=dist[now]+d
                check|={nex}
            elif dist[nex]!=dist[now]+d:
                flag=False
                check=set()
                break
if flag:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N,M=map(int,input().split())
checked=set()
from collections import defaultdict
branch=defaultdict(dict)
flag=True
for i in range(M):
    L,R,D=map(int,input().split())
    branch[L-1][R-1]=D
    branch[R-1][L-1]=-1*D
for i in range(N):
    if i in checked:
        continue
    if not flag:
        break
    dist=dict()
    dist[i]=0
    check={i}
    while len(check)>0:
        now=check.pop()
        checked|={now}
        for nex,d in branch[now].items():
            if nex not in dist.keys():
                dist[nex]=dist[now]+d
                check|={nex}
            elif dist[nex]!=dist[now]+d:
                flag=False
                check=set()
                break
if flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

k = int(input())
seven = 7
count = 0

while True:
    if k % 2 == 0:
        count = -1
        break

    elif seven % k == 0:
        count += 1
        break
    else:
        count += 1
        seven = seven * 10 + 7

print(count)

### FIXED CODE ###

def main():
    k = int(input())
    num = 1
    n = 7

    if (k % 2 == 0):
        print(-1)
        return
    
    for i in range(1000000):
        if (n % k == 0):
            print(num)
            return
        else:
            n = (n*10 + 7) %k
            num += 1
    print(-1)

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

n = int(input())
a = input().split(" ")
a = [int(i) for i in a]

#m = max(a)
r = -1
c = 1
b = []

while 1:
  
  tmp = a
  a = [a[i] for i in range(len(a)) if a[i] <= i+1]
  
  if len(tmp) == len(a):
    break  
  elif c > 1000000:
    print("finite loop")
    break
  else:
    c = c + 1

#print(a)

if len(a) == 0:
  r = -1
else:
  b = [a[0]]
  for i in range(len(a) - 1):
    if a[i+1] == a[i]:
      pass
    elif a[i+1] > a[i] + 1:
      b.append(-1)
    else:
      b.append(a[i+1])

  #print(b)

  for i in range(len(b)):
    t = i + 1
    if t in b:
      idx = b.index(t)
      b = b[(idx+1):]
      r = t
    else:
      break

if r < 0:
  print(r)
else:
  print(n - r)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
 
target = 1
ans = 0
 
for i in range(N):
    if a[i] == target:
        target += 1
    else:
        ans += 1
 
if ans == N:
    ans = -1
    
print(ans)
### BUGGY CODE ###

k = int(input())
ans = 0
import math
from functools import reduce

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

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, b, c)
print(ans)

### FIXED CODE ###

k = int(input())
ans = 0
import math
from functools import reduce

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

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, b, c)
print(ans)
### BUGGY CODE ###

l, r = map(int, input().split(' '))
ary = [num for num in range(l, r+1)]
# print(ary)
ans = 10000

for i in range(len(ary) -1):
  for j in range(i+1, len(ary)):
    tmp = (ary[i] * ary[j]) % 2019
    if tmp < ans:
      ans = tmp
    if ans == 0:
      break

print(ans)

### FIXED CODE ###

l, r = map(int, input().split(' '))
if (r - l) > 2019:
  r = l + 2019
ary = [num for num in range(l, r+1)]
# print(ary)
ans = 10000

for i in range(len(ary) -1):
  for j in range(i+1, len(ary)):
    tmp = (ary[i] * ary[j]) % 2019
    if tmp < ans:
      ans = tmp
    if ans == 0:
      break

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

import numpy as np
from itertools import product

H,W,K = map(int, input().split())
S = np.array([list(map(int,list(input()))) for _ in range(H)]).T
"""
H,W,K = 3,5,2

S = [[1,1,1,0,0],
     [1,0,0,0,1],
     [0,0,1,1,1]]
"""

if np.sum(S)<=K:
    print(0)
else:
    answer = H * W
    for X in product([False,True], repeat=H-1):#分けるか分けないか
        ans = np.sum(X)#横に切った回数
        #print(ans)
        M = [[0]]
        for i, x in enumerate(X):
            if x:
                M.append([])#切った回数箱を増やす
            M[-1].append(i+1)#後ろの箱に切る場所を入れていく
        #print(M)
        D = [0]*len(M)
        #print(D)
        for s in S:
            for k, m in enumerate(M):
                D[k] += np.sum(s[i] for i in m)
                #print("D",D)
            if any(d > K  for d in D):
                ans += 1
                #print("ans",ans)
                D[:] = [np.sum(s[i] for i in m) for m in M]
                
        if answer > ans:
            answer = ans

    print(min(answer,ans))

### FIXED CODE ###


def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0

for i in range(1000):
    c = [i // 100, (i // 10) % 10, i % 10]
    f = 0
    for j in range(n):
        if s[j] == str(c[f]): f+=1
        if f == 3: break
    if f == 3: cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0

for i in range(1000):
    c = [i // 100, (i // 10) % 10, i % 10]
    f = 0
    for j in range(n):
        if s[j] == str(c[f]): f+=1
        if f == 3: break
    if f == 3: cnt += 1
print(cnt)
### BUGGY CODE ###

input()
s=input()
max_len = 0
len_s = len(s)
for i in range(len_s-1):
    if max_len > (len_s-i):
        break
    for j in range(len_s):
        if j-i < max_len:
           continue
        if j-i > len_s - j:
            break
        if s[i:j] not in s[j:]:
            break
        max_len = max(max_len, len(s[i:j]))

print(max_len)

### FIXED CODE ###

N=int(input())
S=input()
a=i=j=0
while j<N:
  if j-i > N-j:
      break  

  t=S[i:j]
  if t in S[j:]:
    a=max(a,len(t))
    j+=1
  else:
    i+=1
print(a)
### BUGGY CODE ###

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

import sys
args = sys.argv

debug_flg = False
def debug(val1,val2="",val3="",val4=""):
    global debug_flg
    if debug_flg:
        print(val1,val2,val3,val4,sep=" , ")

if len(args) != 2:
    n= int(input())
    s= input()
else:
    debug_flg = True
    if args[1] == "2":
        n=39
        s="RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"
    else:
        n=4
        s="RRGB"

ret =0
for i in range(1,n-1):
    for j in range(i,n):
        for k in range(j,n+1):
            if j-i == k-j:
                continue
            if s[i-1] == s[j-1] or s[i-1] == s[k-1] or s[j-1] == s[k-1]:
                continue
            ret += 1

print(ret)

### FIXED CODE ###

def main():
    n= int(input())
    s= input()

    r = s.count("R")
    g = s.count("G")
    b = s.count("B")

    ans = r * g * b
    snum = tuple(s[:])
    for i in range(1,n-1):
        for j in range(i,n):
            k = j * 2 - i
            if k > n:
                break

            if snum[i-1] != snum[j-1] and snum[i-1] != snum[k-1] and snum[j-1] != snum[k-1]:
                ans -= 1

    print(ans)


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

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*P >= g: return 1
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, done=[]):
    global m
    if m <= n: return
    elif point >= g: m = n
    elif flag(point,P[now],now):
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    else:
        if now == -1:
            for i in range(d):
                score(point, n, i, done)
        elif m <= n+P[now]: return
        else:
            done = done[:]
            done.append(now)
            nxtp = point+P[now]*100*(now+1) + C[now]
            for i in range(d):
                if not i in done:
                    score(nxtp, n + P[now], i, done)

score()
print(m)

### FIXED CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*(P-1) >= g: return 1
    elif point+100*(now+1)*P + C[now] >= g: return 2
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, remain = list(range(d))):
    global m
    if m <= n: return
    elif now == -1:
        for i in remain:
            score(point, n, i, remain)
    elif point >= g: m = n
    elif flag(point,P[now],now) == 1:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    elif flag(point,P[now],now) == 2:
        n += P[now]
        if m > n: m = n
    else:
        if m <= n+P[now]: return
        else:
            remain = remain[:]
            remain.remove(now)
            nxtp = point + P[now]*100*(now+1) + C[now]
            for i in remain:
                score(nxtp, n + P[now], i, remain)

score()
print(m)
### BUGGY CODE ###

n=int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
  b=a[i]
  a[i]=0
  print(max(a))
  a[i]=b

### FIXED CODE ###

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

b=sorted(a)

for i in range(n):
  if a[i] != b[-1]:
    print(b[-1])
  else:
    print(b[-2])
### BUGGY CODE ###

n,x,y = map(int,input().split())

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e = [[] for _ in range(n)]
for i in range(n-1):
    e[i].append((1, i+1))
    e[i+1].append((1, i)) # 有向グラフでは削除
e[x-1].append((1, y-1))
e[y-1].append((1, x-1))

d = [dijkstra(i) for i in range(n)]
d = [sorted(d[i][i:]) for i in range(n)]

import bisect

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += bisect.bisect_right(d[j], i) - bisect.bisect_left(d[j], i)
    print(ans)

### FIXED CODE ###

n,x,y = map(int,input().split())

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e = [[] for _ in range(n)]
for i in range(n-1):
    e[i].append((1, i+1))
    e[i+1].append((1, i)) # 有向グラフでは削除
e[x-1].append((1, y-1))
e[y-1].append((1, x-1))

d = [sorted(dijkstra(i)[i:]) for i in range(n)]

import bisect

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += bisect.bisect_right(d[j], i) - bisect.bisect_left(d[j], i)
    print(ans)
### BUGGY CODE ###

n=int(input())

count = 0

for c in range(1,n):
    for a in range(1,n):
        for b in range(1,n):
            if (a*b)+c == n:
                count += 1
else:
    print(count)

### FIXED CODE ###

N = int(input())
ans = 0
for a in range(1, N):
    ans += (N-1)//a
print(ans)
### BUGGY CODE ###

#import
#import math
import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, input().split())) for _ in range(N)]

dp = np.zeros((N+1, W+1), int)

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

print(dp[-1][W])


### FIXED CODE ###

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

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

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) # xで死ぬ
  heappush(q,(t-x,0,x)) # xで死ななくなる
  
D = [int(input()) for _ in range(Q)]
for i,d in enumerate(D):
  heappush(q,(d,2,i))
answer = [-1]*Q

se = set() # 引っかかってる場所

while q:
  a,c,b = heappop(q)
  if not c:
    se.remove(b)
  elif c&1:
    se.add(b)
  else:
    if se:
      answer[b] = min(se)

print('\n'.join(map(str,answer)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  q.append((s-x,1,x)) # xで死ぬ
  q.append((t-x,0,x)) # xで死ななくなる

for i in range(Q):
  d = int(input())
  q.append((d,2,i))
answer = [-1]*Q

se = set() # 引っかかってる場所

q.sort()

min_se = 10**18
flag = False # min_seが正しい

for a,c,b in q:
  if not c:
    se.remove(b)
    if min_se == b:
      flag = False
  elif c&1:
    se.add(b)
    if b < min_se:
      min_se = b
      flag = True
  else:
    if se:
      if not flag:
        min_se = min(se)
        flag = True
      answer[b] = min_se

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

x = int(input())
# 1 <= x <= 10^9
a, b = 0, 0

def make_divisors(n):
    '''約数のリストを返す
    '''
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

d = make_divisors(x)
d.sort()

for i in d:
    #print("div:",i)
    a, b = i, 0
    z = x//i
    while(b != -i):
        #print("sw:",a, b)
        if z == (a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4 ):
            print(a, b)
            exit()
        else:
            a -= 1
            b -= 1


### FIXED CODE ###

x = int(input())
# 1 <= x <= 10^9
a, b = 0, 0

def make_divisors(n):
    '''約数のリストを返す
    '''
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

d = make_divisors(x)
d.sort()

for i in d:
    #print("div:",i)
    a, b = i, 0
    while(b != -1000):
        #print("sw:",a, b)
        if x == pow(a,5) - pow(b,5):
            print(a, b)
            exit()
        else:
            a -= 1
            b -= 1
### BUGGY CODE ###

i = int(input())
c = i
l = []
while c != 1:
	if i % c == 0:
		l.append(c)
	c -= 1
ll = []
for x in l:
	ll.append(i//x)
lll = []
for a,b in zip(l,ll):
	cc = a + b - 2
	lll.append(cc)
print(min(lll))

### FIXED CODE ###

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

l = []
for x, y in zip(sorted(make_divisors(i)), sorted(make_divisors(i),reverse=True)):
	l.append(x + y - 2)
print(min(l))