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

import sys
from itertools import combinations
from math import sqrt

read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N, K, *xyc = map(int, read().split())
    x = xyc[::3]
    y = xyc[1::3]
    xy = list(zip(x, y))
    c = xyc[2::3]
    left = 0
    right = 10 ** 6
    delta = 0.1 ** 7
    while right - left > delta:
        mid = (left + right) / 2
        intersections = xy.copy()
        r = [(mid / i) ** 2 for i in c]
        for i, j in combinations(range(N), 2):
            x1, y1 = xy[i]
            x2, y2 = xy[j]
            X = x2 - x1
            Y = y2 - y1
            XY = X ** 2 + Y ** 2
            r1 = r[i]
            r2 = r[j]

            a = (XY + r1 - r2) / 2
            b = XY * r1 - a ** 2
            if b < delta:
                continue
            b = sqrt(b)
            xi1 = (a * X + Y * b) / XY + x1
            yi1 = (a * Y - X * b) / XY + y1
            xi2 = (a * X - Y * b) / XY + x1
            yi2 = (a * Y + X * b) / XY + y1
            intersections.append((xi1, yi1))
            intersections.append((xi2, yi2))

        cnt = 0
        for X, Y in intersections:
            tmp = 0
            for (i, j), k in zip(xy, r):
                XY = (X - i) ** 2 + (Y - j) ** 2
                if XY < k + delta:
                    tmp += 1
            cnt = max(tmp, cnt)
        if cnt >= K:
            right = mid
        else:
            left = mid

    print(right)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from itertools import combinations
from math import sqrt

read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N, K, *xyc = map(int, read().split())
    x = xyc[::3]
    y = xyc[1::3]
    xy = list(zip(x, y))
    c = xyc[2::3]
    left = 0
    right = 10 ** 6
    delta = 0.1 ** 7
    while right - left > delta:
        mid = (left + right) / 2
        intersections = []
        r = [(mid / i) ** 2 for i in c]
        for i, j in combinations(range(N), 2):
            x1, y1 = xy[i]
            x2, y2 = xy[j]
            X = x2 - x1
            Y = y2 - y1
            XY = X ** 2 + Y ** 2
            r1 = r[i]
            r2 = r[j]

            a = (XY + r1 - r2) / 2
            b = XY * r1 - a ** 2
            if b < delta:
                continue
            b = sqrt(b)
            xi1 = (a * X + Y * b) / XY + x1
            yi1 = (a * Y - X * b) / XY + y1
            xi2 = (a * X - Y * b) / XY + x1
            yi2 = (a * Y + X * b) / XY + y1
            intersections.append((xi1, yi1))
            intersections.append((xi2, yi2))

        intersections.extend(xy)
        cnt = 0
        for X, Y in intersections:
            tmp = 0
            for (i, j), k in zip(xy, r):
                XY = (X - i) ** 2 + (Y - j) ** 2
                if XY < k + delta:
                    tmp += 1
            cnt = max(tmp, cnt)
            if cnt >= K:
                break
        if cnt >= K:
            right = mid
        else:
            left = mid

    print(right)


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

from collections import Counter

N = int(input())
A_array = list(map(int, input().split()))
Ai_dict = Counter(A_array)


def calc_comb(Ai, dictionary):
    num = 0
    for k,v in dictionary.items():
        if v>1:
            if k == Ai:
                N_Ai = v -1 #1こ抜いた数. 
            else:
                N_Ai = v
            num += N_Ai*(N_Ai-1)/2
    return int(num)


res_dict = dict([])

for n in A_array:
    if not n in res_dict.keys():
        res_dict[n] = calc_comb(n, Ai_dict)
        print(calc_comb(n, Ai_dict))
    else:
        print(res_dict[n])


### FIXED CODE ###

from collections import Counter

N = int(input())
A_array = list(map(int, input().split()))
Ai_dict = Counter(A_array)


def calc_comb(dct):
    num = 0
    for k,v in dct.items():
        num += v*(v-1)/2
    return int(num)


res_dict = dict([])
TotalComb = calc_comb(Ai_dict)

for n in A_array:
    if not n in res_dict.keys():
        res_dict[n] = TotalComb - Ai_dict[n]+1
    print(res_dict[n])
### BUGGY CODE ###

import sys
import copy
import  math
import bisect
from statistics import *
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

def bfs():
    d = [[[float("inf")] * w for _ in range(h)] for _ in range(len(kabe))]
    ans = float("inf")
    for i in range(len(kabe)):
        que = deque([])
        que.append((kabe[i][0], kabe[i][1]))
        d[i][kabe[i][0]][kabe[i][1]] = 0
        while que:
            x, y = que.popleft()
            for dx, dy in ([1, 0], [0, 1], [0, -1], [-1, 0]):
                nx = x + dx
                ny = y + dy
                if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[i][nx][ny] == float("inf"):
                    que.append((nx, ny))
                    d[i][nx][ny] = d[i][x][y] + 1
    li = []
    for i in range(h):
        for j in range(w):
            tmp = [d[k][i][j] for k in range(len(kabe))]
            li.append(min(tmp))
    return max(li)

h, w = na()
maze = [list(input()) for _ in range(h)]
kabe = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            kabe.append((i, j))
print(bfs())


### FIXED CODE ###

import sys
import copy
import  math
import bisect
from collections import *
from operator import itemgetter
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

h, w = na()
maze = [list(input()) for _ in range(h)]
que = deque()
d = [[-1] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            d[i][j] = 0
            que.append((i, j))
l = 0

while que:
    x, y = que.popleft()
    l = d[x][y]
    for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        nx = x + dx
        ny = y + dy
        if not 0 <= nx < h or not 0 <= ny < w or d[nx][ny] != -1:
            continue
        d[nx][ny] = l + 1
        que.append((nx, ny))
print(l)
### BUGGY CODE ###

#dj 16D8101012J ito jun
n = int(input())
for _ in range(n):
    a = input()
    b = input()
    na=len(a)
    nb=len(b)
    array = [[0 for i in range(nb+1)] for j in range(na+1)]
    for i in range(1,na+1):
        for j in range(1,nb+1):
            c = 0
            if a[i-1] == b[j-1]:
                array[i][j]=array[i-1][j-1]+1
            else:
                array[i][j] = max(array[i-1][j],array[i][j-1])
    print(array[na][nb])



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###

def main():
    N = int(input())
    ps = list(map(int, input().split(" ")))

    ans = 0
    for i in range(N):
        part = ps[:i+1]
        if min(part) >= ps[i]:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    ps = list(map(int, input().split(" ")))

    ans = 1
    minnum = ps[0]
    for i in range(N):
        if minnum > ps[i]:
            minnum = ps[i]
            ans += 1

    print(ans)

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

N,K=map(int,input().split())
h=[int(input()) for i in range(N)]
h.sort()
res=[]
for i in range(N):
  if i != 0:
    res.append(h[i]-h[i-1])
m=max(res)
for i in range(N-K+1):
  ans=0
  for j in range(K-1):
    ans+=res[j+i]
  if ans<m:
    m=ans
print(m)

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
res=[]
for i in range(N-K+1):
  res.append(h[K+i-1]-h[i])
print(min(res))
### 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()

t = [0]
for i in range(N):
    t.append(t[-1]+1 if S[i:i+2] == "AC" else t[-1])
for i in range(Q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

n = int(input())
l = []
count = 0
for _ in range(n):
    l.append(list(map(lambda x: sorted(x), input().split())))
    for j in range(len(l) - 1):
        if l[-1] == l[j]:
            count += 1
print(count)

### FIXED CODE ###

N = int(input())
dic = {}
 
for i in range(N):
    s = list(input())
    s.sort()
    key = str(s)
    if key in dic:
        dic[key] += 1
    else:
        dic[key] = 1
 
ans = 0
for value in dic.values():
    ans += value*(value-1) / 2
print(int(ans))
### BUGGY CODE ###

x,k,d=map(int,(input().split()))

zx=x
#zzx=zx
for i in range(k):
    xm=abs(x+d)
    xu=abs(x-d)
    x=min(xm,xu)
    k-=1
    if zx+x==d:
        if k%2!=0:
            x=zx
            break
        else:
#            x=zx
            break
#    zzx=zx
    zx=x
    
print(x)      

### FIXED CODE ###

x,k,d=map(int,(input().split()))

x=abs(x)
zx=x
if x<d*k:
    wk,x=divmod(abs(x),d)
    k-=wk    
else:
    x-=d*k
    k=0

for i in range(k):
    xm=abs(x+d)
    xu=abs(x-d)
    x=min(xm,xu)
    k-=1
    if zx+x==d:
        if k%2!=0:
            x=zx
            break
        else:
            break
    zx=x
    
print(x)
### BUGGY CODE ###

N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if j > 0:
            r[i][j] = r[i][j-1] + p[i][j]
        else:
            r[i][j] = p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
        if j - 1> 0:
            q = q - r[j-1][j-2]
    print(q)

### FIXED CODE ###

N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if i == 0:
            r[i][j] = p[i][j] + r[i][j-1]      
        elif j == 0:
            r[i][j] = p[i][j] +r[i-1][j]
        else:
            r[i][j] = r[i-1][j] + r[i][j-1] - r[i-1][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    if Qlist[i][0] == 1:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1]
    else:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1] - r[Qlist[i][0]-2][Qlist[i][1]-1]
    print(b)
### BUGGY CODE ###

N = int(input())
A= list(map(int,input().split()))
mod_num = 1.0e+9 + 7
rest = 0
for i in range(N-1):
  for j in range(N-i-1):
    rest +=(A[i]%mod_num)*(A[i+j+1]%mod_num)
    rest=rest%mod_num

print(int(rest%mod_num))

### FIXED CODE ###

N = int(input())
A= list(map(int,input().split()))
mod_num = int(1.0e+9 + 7)
rest = 0
temp = 0

for i in range(N-1):
  temp+=A[i]
  rest += temp*A[i+1]
  rest = rest%mod_num

print(int(rest%mod_num))
### BUGGY CODE ###

import math
from functools import reduce

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

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

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

if gcd(*A_list) != 1:
    print("not coprime")
else:
    for i in range(len(A_list)):
        for j in range(i+1, len(A_list)):
            if gcd(A_list[i], A_list[j]) != 1:
                print("setwise coprime")
                exit()
    print("pairwise coprime")



### FIXED CODE ###

import math
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 # 0をpairwise coprime

for a in A:
    memo[a] += 1

for i in range(2, L): # すべてでgcdが1ということは、対象の数字ごとのステップに数字がないことと同じ
    if sum(memo[i::i]) > 1: # memo[i] + memo[2i] +... + memo[ni] memo[i]の倍数があれば sum は 2 以上になる
        flag = 1
        break

g = 0
for i in range(N):
    g = math.gcd(g, A[i])

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)
### BUGGY CODE ###

s=[ord(ch) for ch in input()]
t=[ord(ch) for ch in input()]

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz ]
t=[ z for z in t if z in mnmz ]
if len(s)>len(t): s, t = t, s

# init
dp=[[0]*len(s) for _ in range(len(t))]

#dp frame

for i in range(len(s)): 
    if s[i]==t[0]:
        for j in range(i, len(s)):
            dp[0][j]=1
        break
for i in range(len(t)): 
    if s[0]==t[i]:
        for j in range(i, len(t)):
            dp[j][0]=1
        break
#dp
for i in range(1,len(t)):
    for j in range(1, len(s)):
        temp = max(dp[i][j-1], dp[i-1][j])
        if s[j]==t[i]:
            if temp<dp[i-1][j-1]+1:
                temp=dp[i-1][j-1]+1
        dp[i][j]=temp
    if dp[i][-1]==len(s): break

#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>0 and j>0:
    if s[j]==t[i] and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)
if i==0:
    res.append(t[0])
elif j==0:
    res.append(s[0])


print("".join(chr(i) for i in reversed(res)))



### FIXED CODE ###

s=[ord(ch)-97 for ch in input()]
t=[ord(ch)-97 for ch in input()]

# minimize
mnmz={ch for ch in s} & {ch for ch in t}
if len(mnmz)==0:
    print("")
    exit()
s=[ z for z in s if z in mnmz ]
t=[ z for z in t if z in mnmz ]
if len(s)>len(t): s, t = t, s

# init
dp=[[0]*len(s) for _ in range(len(t))]

#dp frame init
for i in range(len(s)): 
    if s[i]==t[0]:
        for j in range(i, len(s)):
            dp[0][j]=1
        break
for i in range(len(t)): 
    if s[0]==t[i]:
        for j in range(i, len(t)):
            dp[j][0]=1
        break
#dp
for i in range(1,len(t)):
    for j in range(1, len(s)):
        if s[j]==t[i]:
            dp[i][j]=dp[i-1][j-1]+1
        else: dp[i][j]=(dp[i][j-1] if dp[i][j-1]>dp[i-1][j] else dp[i-1][j])

#recover string
res=[]
j=len(s)-1
i=len(t)-1
while i>=0 and j>=0:
    if s[j]==t[i]: #and dp[i][j]==dp[i-1][j-1]+1:
        res.append(s[j])
        i=i-1
        j=j-1
        continue
    if i==0 and j==0: break
    if j>0 and dp[i][j]==dp[i][j-1]:
        j=j-1
    else: i=i-1
# last letter (first acually)


print("".join(chr(i+97) for i in reversed(res)))
### BUGGY CODE ###


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

flg = False

# iは10000円札の枚数、jは5000円札の枚数、kは1000円札の枚数
for i in range(n + 1):
    for j in range(n + 1 - i):
        for k in range(n + 1 - i - j):
            if 10000 * i + 5000 * j + 1000 * k == y and i + j + k == n and not flg:
                flg = True
                print(i, j, k)
                break
        else:
            continue
        break
    else:
        continue
    break

if not flg:
    print(-1, -1, -1)


### FIXED CODE ###


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

flg = False

# iは10000円札の枚数、jは5000円札の枚数、kは1000円札の枚数
for i in range(n + 1):
    for j in range(n + 1 - i):
        k = (y - 10000 * i - 5000 * j) // 1000
        if i + j + k == n and not flg:
            flg = True
            print(i, j, k)
            break
    else:
        continue
    break

if not flg:
    print(-1, -1, -1)
### BUGGY CODE ###

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

for i in range(n):
    ans *= a[i]

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

### FIXED CODE ###

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

if 0 in a:
    print(0)
    exit()

for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()

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

n = int(input())
z = []
for i in range(n):
    x, y = [int(x) for x in input().split()]
    z.append([x, y])
    z.sort(reverse=True)

a = []
b = []
for i in range(n // 2):
    a.append(z[2 * i][0])
    b.append(z[2 * i + 1][1])
if n % 2 == 1:
    a.append(z[len(z) - 1][0])

print(sum(a) - sum(b))


### FIXED CODE ###

n = int(input())
#z = [[int(x) for x in input().split()] for i in range(n)]
z = []
t = 0
for i in range(n):
    x, y = [int(x) for x in input().split()]
    t += y
    z.append(x + y)
z.sort(reverse=True)

s = 0
for i in range(n // 2):
    s += z[2 * i]
if n % 2 == 1:
    s += z[len(z) - 1]

print(s - t)

#アルゴリズムが間違っている
### BUGGY CODE ###

K,S = (int(x) for x in input().split())
count = 0
for x in range(K+1):
  if x>S:
    break
  for y in range(K+1):
    if y > S:
      break
    for z in range(K+1):
      if x+y+z == S:
        count += 1
      elif z > S:
        break

print(count)

### FIXED CODE ###

K,S = (int(x) for x in input().split())
count = 0
for x in range(K+1):
  for y in range(K+1):
    remain = S-x-y
    if 0 <= remain and remain <= K:
      count += 1

print(count)
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
hw = [input() for i in range(h)]
#for i in range(h):
#    hw.append(input())

# used = [True]*h*w
isWhite = [[True]*w for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if hw[i][j] == '#':
            queue.append([i,j,0])# h, w, step count
            isWhite[i][j] = False

res = 0
while len(queue) > 0:
    ph, pw, pcnt = queue.popleft()
    if ph > 0 and isWhite[ph-1][pw]:
        queue.append([ph-1, pw, pcnt+1])
        isWhite[ph-1][pw] = False
    if ph < h-1 and isWhite[ph+1][pw]:
        queue.append([ph+1, pw, pcnt+1])
        isWhite[ph+1][pw] = False
    if pw > 0 and isWhite[ph][pw-1]:
        queue.append([ph, pw-1, pcnt+1])
        isWhite[ph][pw-1] = False
    if pw < w-1 and isWhite[ph][pw+1]:
        queue.append([ph, pw+1, pcnt+1])
        isWhite[ph][pw+1] = False
#        print(queue)
    res = pcnt
print(res)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())

field = [] # 白黒情報を持つリスト
mark = [] # 操作回数を保持するリスト
INF = 10**6

for i in range(h):
    field.append(list(input()))
    mark.append([0 for i in range(w)])

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            queue.append([i, j])

while len(queue) > 0:
    y, x = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= ny < h and 0 <= nx < w:
            if field[ny][nx] == ".":
                mark[ny][nx] = mark[y][x] + 1
                queue.append([ny, nx])
                field[ny][nx] = "#"

ans=0

for i in mark:
    ans = max(ans, max(i))

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

N = int(input())
A = list(map(int, input().split()))
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a

gcd_ref = [A[0]]

for i in range(1, N):
    new_gcd = gcd(gcd_ref[-1], A[i])
    gcd_ref.append(new_gcd)
    
best = gcd_ref[N - 1]
for i in range(N - 1, -1, -1):
    if i > 0:
        if i == N - 1:
            a = gcd_ref[i - 1]
            if best < a:
                best = a
        else:
            a = gcd_ref[i - 1]
            l = A[i + 1:]
            gcd_without_i = gcd(a, gcdlist(l))
            if gcd_without_i > best:
                best = gcd_without_i
    else:
        l = A[1:]
        gcd_without_i = gcdlist(l)
        if gcd_without_i > best:
            best = gcd_without_i

print(best)
    

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

gcd_L = [A[0]]
gcd_R = [A[N - 1]]

for i in range(1, N):
    new_gcd_l = gcd(gcd_L[-1], A[i])
    gcd_L.append(new_gcd_l)
    new_gcd_r = gcd(gcd_R[-1], A[N - i - 1])
    gcd_R.append(new_gcd_r)
    
best = gcd_L[N - 1]
for i in range(N):
    if i > 0:
        if i == N - 1:
            a = gcd_L[i - 1]
            if best < a:
                best = a
        else:
            l = gcd_L[i - 1]
            r = gcd_R[N - 2 - i]
            gcd_without_i = gcd(l, r)
            if gcd_without_i > best:
                best = gcd_without_i
    else:
        a = gcd_R[N - 2]
        if a > best:
            best = a

print(best)
### BUGGY CODE ###

def main():
    n = int(input())
    # d,t,s = map(int, input().split())
    a = list(map(int, input().split()))
    # s = input()

    sm = 0
    for i in range(len(a)):
        for j in range(i+1,len(a)):
            sm += (a[i]% (10**9+7) * a[j% (10**9+7)]) % (10**9+7)
    
    print(sm% (10**9+7))




if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    # d,t,s = map(int, input().split())
    a = list(map(int, input().split()))
    # s = input()
    mod = 10**9+7

    s = sum(a)

    sm = 0

    for i in a:
        s -= i
        sm += i * s % mod

    print(sm % mod)


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

n = int(input())
p = list(map(int, input().split()))
ans = n
for i in range(1,n):
    if i> n- p[i]:
        ans -=1
    else:
        for j in range(i+1):
            r = True
            if p[i]>p[j]:
                ans -=1
                break
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
ans = 0
m = 200001
for i in p:
    if i<m:
        ans+=1
        m=i
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
z=list(map(int,input().split()))
a,b,c=[],[],z[2]-z[1]
for i in range(z[2]):
    a.append(int(input()))
for i in range(z[0]):
    b.append(a.count(i+1))
for i in range(z[0]):
    if c-b[i]>=0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n,k,q=map(int,input().split())
a,b=[int(input()) for _ in range(q)],[0]*n
for i in a:
    b[i-1]+=1
for i in b:
    print('Yes' if i+k-q>0 else 'No')
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
#n個のまち
#1～n　番号
#テレポーターありゅううううううう
# iの転送先a[i]
# kがすこおおおおおおおおおおおお
# k回テレポートつかうとどのまちいく？

# modるか
# nは2*10**5

machi = 1
toutatu = []
while not machi in toutatu:
	toutatu.append(machi)
	machi = a[machi-1]
saigo = machi
num = toutatu.index(saigo)
unchi = toutatu[num:]
cnt = len(unchi)
num = toutatu.index(saigo)

if num > k:
	print(toutatu[k])
else:
	print(unchi[(k-num)%cnt])

### FIXED CODE ###

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

machi = 1
toutatu = []
pypyosoi = set()
while not machi in pypyosoi:
	toutatu.append(machi)
	pypyosoi.add(machi)
	machi = a[machi-1]

saigo = machi
num = toutatu.index(saigo)
unchi = toutatu[num:]
cnt = len(unchi)

if num > k:
	print(toutatu[k])
else:
	print(unchi[(k-num)%cnt])

#pypyが遅いのは自分のコードが悪いだけごめんねpypyちゃん