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

import copy
N = int(input())
X = list(map(int,input().split()))
Y = copy.deepcopy(X)
for i in range(N):
  del Y[i]
  Y.sort()
  print(Y[(N-1)//2])
  Y = copy.deepcopy(X)


### FIXED CODE ###

import copy
N = int(input())
X = list(map(int,input().split()))
XX = copy.deepcopy(X)
XX.sort()
X1 = XX[(N//2)-1]
X2 = XX[N//2]
if X1 == X2:
  for i in range(N):
    print(X1)
else:
  Y = float(X1 + X2)
  Y = Y/2
  for i in range(N):
    if X[i] > Y:
      print(X1)
    else:
      print(X2)
### BUGGY CODE ###

import math
import fractions
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

def is_prime(num):
    for i in range(2, num):  # 第二引数は sqrt(num)+1 でも良い
        if num % i == 0:
            return False

    return True

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

g = fractions.gcd(A, B)

# print(g)
div = make_divisors(g)
# print(div)
p = [i for i in div if is_prime(i)]
# print(p)
print(len(p))
# 2

### FIXED CODE ###

import math
import fractions
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

def is_prime(p):
    if p == 1:
        return False
    for i in range(2,int(p ** .5) + 1):
        if p % i == 0:
            return False
    return True

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

g = fractions.gcd(A, B)

div = make_divisors(g)
ans = 1
for i in div:
    if is_prime(i):
        ans += 1
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
d=[]
for _ in range(m):
    b,c=map(int,input().split())
    for _ in range(b):
    	d.append(c)

d=sorted(d,reverse=True)

total=0
for i in range(n):
  total+=a[i]
  
right=total
left=0

for i in range(min(n,len(d))):
    if a[i]<d[i]:
        left+=d[i]
        right-=a[i]
    else:
        break
print(right+left)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
arr=[]

for i in range(m):
    b,c=map(int,input().split())
    arr.append((b,c))

a=sorted(a)
arr=sorted(arr,key=lambda x:-x[1])

flag=0
left=0
for tup in arr:
    for i in range(left,min(left+tup[0],n)):
        if tup[1]>a[i]:
            a[i]=tup[1]
        else:
            flag=-1
            break
        if i==n-1:
            flag=-1
            break
    left+=tup[0]
    if flag==-1:
        break

print(sum(a))
### BUGGY CODE ###

import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        for i, a_i in enumerate(a[start:start+count+1]):
            if a_i < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[start+i] = ope
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)

### FIXED CODE ###

import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        i = 0
        for a_i in xrange(start, start+count):
            if a_i >= n:
                break
            if a[a_i] < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[a_i] = ope
                i += 1
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)
### BUGGY CODE ###

n = int(input())
s = map(int, input())

dp = tuple([0] * 1000 for _ in range(4))
dp[0][0] = 1
# dp[x][int(str)]:=x文字のstrは構成可能か？0/1

for x in s:
    for k in range(2, -1, -1):
        for incomplete_key in range(100):
            dp[k + 1][incomplete_key * 10 + x] |= dp[k][incomplete_key]

print(sum(dp[3]))

# dp


### FIXED CODE ###

def main():
    from collections import defaultdict

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

    d = defaultdict(bool)

    for c in s:
        for x in '0123456789':
            for y in '0123456789':
                if d[x + y]:
                    d[x + y + c] = True
        for x in '0123456789':
            if d[x]:
                d[x + c] = True
        d[c] = True

    print(sum(len(k) == 3 for k in d))


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

from collections import defaultdict
N,P=map(int,input().split())
S=input()

if P==2 or P==5:
    ans=0
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)

else:
    d=defaultdict(int)
    for i in range(N):
        a=int(S[N-i-1:N])%P
        d[a]+=1
    ans=d[0]
    for v in d.values():
        ans+=v*(v-1)//2
    print(ans)
    


### FIXED CODE ###

from collections import defaultdict
N,P=map(int,input().split())
S=input()

if P==2 or P==5:
    ans=0
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)

else:
    d=defaultdict(int)
    a=0
    for i in range(N):
        a+=int(S[N-i-1])*pow(10,i,P)
        a%=P
        d[a]+=1
    ans=d[0]
    for v in d.values():
        ans+=v*(v-1)//2
    print(ans)
### BUGGY CODE ###

n = int(input())
sum1 = 0
for i in range(len(str(n))):
    sum1 += int(str(n)[i])
if sum1 % 9 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
s = str(n)
array = list(map(int, s))
if sum(array) % 9 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

result = 0

if n <= 2:
    print(0)
    
for i in range(n-2):
    if s[i] == "R":
        for j in range(i+1, n-1):
            if s[j] == "G":
                for k in range(j+1, n):
                    if s[k] == "B":
                        if j-i != k-j:
                            result += 1
            elif s[j] == "B":
                for k in range(j+1, n):
                    if s[k] == "G":
                        if j-i != k-j:
                            result += 1
    if s[i] == "G":
        for j in range(i+1, n-1):
            if s[j] == "R":
                for k in range(j+1, n):
                    if s[k] == "B":
                        if j-i != k-j:
                            result += 1
            elif s[j] == "B":
                for k in range(j+1, n):
                    if s[k] == "R":
                        if j-i != k-j:
                            result += 1
    if s[i] == "B":
        for j in range(i+1, n-1):
            if s[j] == "R":
                for k in range(j+1, n):
                    if s[k] == "G":
                        if j-i != k-j:
                            result += 1
            elif s[j] == "G":
                for k in range(j+1, n):
                    if s[k] == "R":
                        if j-i != k-j:
                            result += 1
print(result)

### FIXED CODE ###

n = int(input())
s = input()
 
result = 0
 
if n <= 2:
    print(0)

for i in range(n-2):
    if s[i] == "R":
        a = s[i+1:].count("G")
        b = s[i+1:].count("B")
        result += a*b
        for j in range(1, (n+1-i)//2):
            if (s[i+j] == "G" and s[i+2*j] == "B") or (s[i+j] == "B" and s[i+2*j] == "G"):
                result -= 1
    elif s[i] == "G":
        a = s[i+1:].count("R")
        b = s[i+1:].count("B")
        result += a*b
        for j in range(1, (n+1-i)//2):
            if (s[i+j] == "R" and s[i+2*j] == "B") or (s[i+j] == "B" and s[i+2*j] == "R"):
                result -= 1
    elif s[i] == "B":
        a = s[i+1:].count("R")
        b = s[i+1:].count("G")
        result += a*b
        for j in range(1, (n+1-i)//2):
            if (s[i+j] == "R" and s[i+2*j] == "G") or (s[i+j] == "G" and s[i+2*j] == "R"):
                result -= 1
print(result)
### BUGGY CODE ###

n,m=map(int,input().split())
edg=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    edg[a].append(b)
    edg[b].append(a)
visited=[False for i in range(n)]
visited[0]=True
parent=[None for i in range(n)]
st=[0]
while st!=[]:
    now=st[0]
    del(st[0])
    for i in edg[now]:
        if not visited[i]:
            st.append(i)
            visited[i]=True
            parent[i]=now
print("Yes")
for i in parent[1:]:
    print(i+1)


### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
edg=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1;b-=1
    edg[a].append(b)
    edg[b].append(a)
visited=[False for i in range(n)]
visited[0]=True
parent=[None for i in range(n)]
q=deque([0])
while len(q)>0:
    now=q.popleft()
    for i in edg[now]:
        if not visited[i]:
            q.append(i)
            visited[i]=True
            parent[i]=now
print("Yes")
for i in parent[1:]:
    print(i+1)
### BUGGY CODE ###

def gcd(a,b):
    if(a%b==0):
        return b
    else:
        return gcd(b,a%b)

k = int(input())
val = [[0]*(k+1) for i in range(k+1)]
sum = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        if(val[i][j] == 0):
            val[i][j] = gcd(i,j)
        for l in range(1,k+1):
            if(val[val[i][j]][l] == 0):
                val[val[i][j]][l] = gcd(val[i][j],l)
            sum = sum + val[val[i][j]][l]

print(sum)

### FIXED CODE ###

def gcd(a,b):
    if(a%b==0):
        return b
    else:
        return gcd(b,a%b)
 
k = int(input())
val = [[0]*(k+1) for i in range(k+1)]
sum = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        if(val[i][j] == 0):
            val[i][j] = gcd(i,j)
        for l in range(1,k+1):
            if(val[val[i][j]][l] == 0):
                val[val[i][j]][l] = gcd(val[i][j],l)
            sum = sum + val[val[i][j]][l]
 
print(sum)
### BUGGY CODE ###

n,m=map(int,input().split())
tasks=[None]*n
for i in range(n):
  a,b=map(int,input().split())
  tasks[i]=[a,b]

tasks=sorted(tasks,key=lambda x:x[1],reverse=True)
ans=0
for i in range(m,-1,-1):
  left=m-i
  for j in range(len(tasks)):
    if tasks[j][0]<=left:
      ans+=tasks.pop(j)[1]
      break

print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
tasks=[None]*n
for i in range(n):
  a,b=map(int,input().split())
  tasks[i]=[a,b]

tasks=sorted(tasks,key=lambda x:x[0])
import heapq
que=[]
ans=0
heapq.heapify(que)
j=0
for i in range(m,-1,-1):
  left=m-i
  while j<len(tasks):
    if tasks[j][0]<=left:
      heapq.heappush(que, tasks[j][1]*(-1))
    else:
      break
    j+=1
  if len(que)>0:
    val=heapq.heappop(que)*(-1)
    ans+=val
      
print(ans)
### BUGGY CODE ###

import numpy as np


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

W = np.array(waterlist)
# print(W)

# print(waterlist)
# print(volume)
matrix = [[] for _ in range(N)]
for i in range(N):
    templist = [0 for _ in range(N)]
    templist[i] = 1
    if i == N - 1:
        templist[0] = 1
    else:
        templist[i + 1] = 1
    matrix[i] = templist


A = np.array(matrix)
inv_A = np.linalg.inv(A)
# print(inv_A)

ansmatrix = inv_A.dot(W)*2
# print(ansmatrix)
message = ""
for i in range(N):
    message += str(int(ansmatrix[i]))
    if i == (N - 1):
        break
    message += " "
print(message)


### FIXED CODE ###



N = int(input())
waterlist = list(map(int, input().split()))
mountain = [0 for _ in range(N)]
S = 0
for i in range(N):
    S += waterlist[i]
# print(S)
x1 = S
for i in range(1, N, 2):
    x1 -= waterlist[i] * 2
mountain[0] = x1
# print(x1)
for i in range(1, N):
    mountain[i] = 2*waterlist[i-1]-mountain[i-1]

# print(mountain)
# A = np.array(matrix)
# inv_A = np.linalg.inv(A)
# # print(inv_A)

# ansmatrix = inv_A.dot(W)*2
# # print(ansmatrix)
message = ""
for i in range(N):
    message += str(int(mountain[i]))
    if i == (N - 1):
        break
    message += " "
print(message)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
t=[]
for i in range(N):
    ans+=t.count(A[i]-i)
    t.append(-A[i]-i)
print(ans)

### FIXED CODE ###

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

import functools
import math
import fractions

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

#gcd_all = functools.reduce(math.gcd, A)
gcd_all = functools.reduce(fractions.gcd, A)
#print(gcd_all)

for i in range(N):
    list = A[:i] + A[i+1:]
    #print(list)
    #gcd_1 = functools.reduce(math.gcd, list)
    gcd_1 = functools.reduce(fractions.gcd, list)
    #print(gcd_1)
    if gcd_1 >= gcd_all:
        index = i
        value = gcd_1
        gcd_all = gcd_1

A[index] = value

#print(functools.reduce(math.gcd, A))
print(functools.reduce(fractions.gcd, A))



### FIXED CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

L = [0] * (N+1)
R = [0] * (N+1)
for i in range(N):
    L[i+1] = gcd(L[i], A[i])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

max_m = 0
for i in range(N):
    m = gcd(L[i], R[i+1])
    if max_m < m:
        max_m = m
print(max_m)
### BUGGY CODE ###

import sys
for line in sys.stdin:
    n=int(line)
    plist = [1 for i in xrange(n+1)]
    plist[0]=0
    plist[1]=0
    for x in xrange(n):
        if plist[x] == 1:
            i=2
            while x*i < len(plist):
                plist[x*i] = 0
                i+=1
    print plist.count(1)

### FIXED CODE ###

#! -*- coding:utf-8 -*-
import sys
# import time
for line in sys.stdin:
  n=int(line)
  # n=input()
  # start = time.time()
  #plist = [1 for i in xrange(n+1)]
  #??¨??¨1???????????????
  #1?????¨???????????????????´???°??¨??????
  plist = [1]*(n+1)
  #0??¨1????´???°?????????????????§0???????????????
  plist[0]=plist[1]=0
  i=2
  #??¶??°????????????????????????
  while True:
      pos0 = 2*i
      if pos0 < len(plist):
          plist[pos0] = 0
      else:
          break
      i+=1
  #???????????¨????????????????????????
  for x in xrange(3,int(n**0.5)+1):
    if plist[x]:
      for pos0 in xrange(x**2,n+1,x):
        plist[pos0] = 0
  # elapsed_time = time.time()-start
  # print elapsed_time
  print plist.count(1)
### BUGGY CODE ###

# coding:utf-8

INF = float('inf')


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


N, M = inpl()

n = M // N
while n > 0:
    if M % n == 0:
        print(n)
        break
    else:
        n -= 1


### FIXED CODE ###

# coding:utf-8


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


N, M = inpl()

n = M // N
while n > 0:
    if M % n == 0:
        print(n)
        break
    else:
        n -= 1
### BUGGY CODE ###

import sys, copy, math, collections, itertools

n, k = (int(i) for i in input().split())
hs = [int(input()) for i in range(n)]
hs.sort()
i=0
m=-1
l=len(hs)
while True:
    if l < (i+k):
        break
    tmp = hs[i:i+k]
    cnd=tmp[-1] - tmp[0]
    if m==-1:
        m=cnd
    else:
        if cnd < m:
            m=cnd
    i+=1
print(int(m))


### FIXED CODE ###

import sys, copy, math, collections, itertools

n, k = (int(i) for i in input().split())
hs = [int(input()) for i in range(n)]
hs.sort()
i=0
m=-1
l=len(hs)
while True:
    if l < (i+k):
        break
    # tmp = hs[i:i+k]
    cnd=hs[i+k-1] - hs[i]
    if m==-1:
        m=cnd
    else:
        if cnd < m:
            m=cnd
    i+=1
print(int(m))
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(n):
    ans += i

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(n):
    ans += i

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

H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)

table = [-1] * (H * W + 1)
# def calc(table, l, r, m):
#     if table[l] != -1:
#         return table[l][r]
#     m_ = abs(A[l+D][0] - A[l][0]) + abs(A[l+D][1] - A[l][1])
#     table[l][l+D] = m_
# print(table)

Q = int(input())
for q in range(Q):
    l, r = [int(x) for x in input().split()]
    m = 0
    while l != r:
        if table[l] == -1:
            table[l] = abs(A[l+D][0] - A[l][0]) + \
                       abs(A[l+D][1] - A[l][1])
        m += table[l]
        l = l + D
    print(m)


### FIXED CODE ###

H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)

table = [0] * (H * W + 1)
for i in range(D):
    x = H * W - i - D
    r = 0
    while x > 0:
        table[x] = abs(A[x][0] - A[x+D][0]) + abs(A[x][1] - A[x+D][1]) \
                   + r
        r = table[x]
        x -= D
for q in range(int(input())):
    l, r = [int(x) for x in input().split()]
    print(table[l] - table[r])
### BUGGY CODE ###

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

d = []

for v in p:
    d.append((1+v)/2)

r=0

for i in range(n-k+1):
    r=max(r,sum(d[i:i+k]))


print(r)


### FIXED CODE ###

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

d = []

for v in p:
    d.append((1+v)/2)

x=r=sum(d[:k])
# print(d)

for i in range(1,n-k+1):
    # r=max(r,sum(d[i:i+k]))
    x=x-d[i-1]+d[i+k-1]
    r=max(r,x)
    # print(r,i)

print(r)
### BUGGY CODE ###

X, Y, A, B, C = map(int, input().split())
p = [int(a) for a in input().split()]
q = [int(a) for a in input().split()]
r = [int(a) for a in input().split()]
s = []

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

for i in range(X):
    s.append(p.pop(0))
for i in range(Y):
    s.append(q.pop(0))
s.sort()
for i in range(C):
    if(s[0] < r[0]):
        s.pop(0)
        s.append(r.pop(0))
        
print(sum(s))

### FIXED CODE ###

X, Y, A, B, C = map(int, input().split())
p = [int(a) for a in input().split()]
q = [int(a) for a in input().split()]
r = [int(a) for a in input().split()]
s = []

p.sort(reverse=True)
q.sort(reverse=True)

p = p[:X]
q = q[:Y]
s = p + q + r
s.sort(reverse=True)

s = s[:(X + Y)]
        
print(sum(s))
### BUGGY CODE ###

import math, collections

def f(c):
  sum=0
  for i in c.values():
    sum+=g(i,2)
  return sum

def g(n,r):
  if n==0 or n==1:return 0
  else:return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

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

for i in range(n):
  l=[]
  l.extend(k)
  del l[i]
  c=collections.Counter(l)
  print(f(c))

### FIXED CODE ###

import collections
n=int(input())
k=list(map(int,input().split()))
c=collections.Counter(k)
ans=0

for i in c.values():
  ans+=i*(i-1)//2

for i in range(n):
  print(ans-c[k[i]]+1)
### BUGGY CODE ###

N = int(input())
L = []
for l in range(N):
	L.append(int(input()))
	
maxL = [0] * N
	
for i in range(N):
	a = L[i]
	L[i] = 0
	maxL[i] = max(L)
	L[i] = a
	
for i in maxL:
	print(i)

### FIXED CODE ###

N = int(input())
L = []
for l in range(N):
	L.append(int(input()))

maxL = max(L)
subL = L
num = ["n"] * N

if L.count(maxL) >= 2:
	for i in range(N):
		print(maxL)
		
else:	
	for i in range(N):
		if L[i] == maxL:
			L[i] = 0
			print(max(L))
		else:
			print(maxL)
### BUGGY CODE ###

#import sys
#sys.setrecursionlimit(10**8)
from collections import deque

n, m = map(int, input().split())
depth = [0 for _ in range(n)]
chil = [[] for _ in range(n)]
rank = [0 for _ in range(n)]
parent = [-1 for _ in range(n)]
visited = [False for _ in range(n)]
for _ in range(n+m-1):
	a, b = map(int, input().split())
	chil[a-1].append(b-1)
	rank[b-1] += 1

#print(chil)
for i in range(n):
	if rank[i] == 0:
		par = i
		break

parent[par] = -1

def bfs(x):
	que = deque([[x, 0]])
	while que:
		l = que.pop()
		y, d = l[0], l[1]
		for c in chil[y]:
			if depth[c] == -1:
				depth[c] = d+1
				parent[c] = y
				que.appendleft([c, d+1])
			elif depth[c] < d+1:
				depth[c] = d+1
				parent[c] = y
				que.appendleft([c, d+1])

	return

bfs(par)
#def dfs(x, d):
#	for c in chil[x]:
#		if depth[c] == -1:
#			depth[c] = d+1
#			parent[c] = x
#			dfs(c, d+1)
#		elif depth[c] < d+1:
#			depth[c] = d+1
#			parent[c] = x
#			dfs(c, d+1)
#
#	return
#
#dfs(par, 0)

for p in parent:
	print(p+1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
#from collections import deque

n, m = map(int, input().split())
depth = [0 for _ in range(n)]
chil = [[] for _ in range(n)]
rank = [0 for _ in range(n)]
parent = [-1 for _ in range(n)]
#visited = [False for _ in range(n)]
for _ in range(n+m-1):
	a, b = map(int, input().split())
	chil[a-1].append(b-1)
	rank[b-1] += 1

#print(chil)
for i in range(n):
	if rank[i] == 0:
		par = i
		break

parent[par] = -1

#def bfs(x):
#	que = deque([[x, 0]])
#	while que:
#		l = que.pop()
#		y, d = l[0], l[1]
#		print(y, d)
#		if d < depth[y]:
#			continue
#		for c in chil[y]:
#			if depth[c] == -1:
#				depth[c] = d+1
#				parent[c] = y
#				que.appendleft([c, d+1])
#			elif depth[c] < d+1:
#				depth[c] = d+1
#				parent[c] = y
#				que.appendleft([c, d+1])
#
#	return

#bfs(par)

def dfs(x):
	true_chil = []
	for c in chil[x]:
		if rank[c] == 1:
			true_chil.append(c)
		else:
			rank[c] -= 1
	for t in true_chil:
		parent[t] = x
		dfs(t)

	return

dfs(par)

for p in parent:
	print(p+1)
### BUGGY CODE ###

# D

N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (W+1) for _ in range(N)]
for i in range(N):
    for j in range(W+1):
        if j >= w[i]:
            dp[i][j] = max(dp[i-1][j-w[i]] + v[i], dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(max(dp[-1]))

### FIXED CODE ###

# D
import numpy as np
n,w = map(int, input().split())
 
items = list(map(int, input().split()) for _ in [0]*n)
dp = np.zeros(w+1, dtype='int64')
 
for weight, value in items:
    dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)
print(dp.max())
### BUGGY CODE ###

import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
n=int(input())
a=list(map(int, input().split()))
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        ans+=a[i]*a[j]
        if ans>10**9+7:
            ans%=10**9+7
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
n=int(input())
a=list(map(int, input().split()))
ans=0
anss=[0]*(n+1)
for i in range(1,n+1):
    anss[-i-1]=anss[-i]+a[-i]
    if anss[-i-1]>10**9+7:
        anss[-i-1]%=10**9+7
#print(anss)
for i in range(n-1):
    ans+=a[i]*anss[i+1]
    if ans>10**9+7:
        ans%=10**9+7
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a[0]

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

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

print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a[0]

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

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


print(ans)