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

n = int(input())
print(0, flush=True)

for i in [0, n - 1]:
    res = input()
    if res == "Vacant":
        exit()


left = 0
right = n - 1
gen = res


while abs(right - left) > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()
    
    if res == "Vacant":
        exit()
    
    if (right - mid) % 2 == 0:
        if gen == res:
            right = mid
        else:
            left = mid
    else:
        if gen != res:
            right = mid
        else:
            left = mid

### FIXED CODE ###

n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid
### BUGGY CODE ###

N=int(input())
A=[i for i in map(int,input().split())]
mini=min(A)
while mini>0:
    for i in range(len(A)):
        if A[i]!=mini:
            A[i]=A[i]%mini
    z=A.count(0)
    A=sorted(A)[z:]
    m=A[0]
    if m==1:
        break
    else:
        if [i%m for i in A]==[0]*len(A):
            break
print(A[0])


### FIXED CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
m = min(A)
while m > 0:
    for i in range(0,len(A)):
        if A[i] != m:
            A[i] = A[i]%m
    z = A.count(0)
    A = sorted(A)[z:]
    m = A[0]
    if m == 1:
        break
    else:
        if [_%m for _ in A] == [0]*len(A):
            break
print(m)
### BUGGY CODE ###

N = int(input())
nums = [int(e) for e in input().split()]
nums.sort()

for i in range (1,N+1):
    c = 0
    for j in range(0,len(nums)):
        if nums[j] == i:
            c = c + 1
    print(c)
    del nums[:int(c)]

### FIXED CODE ###

import collections as col

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

List = col.Counter(List)
Count_List = [0]*n
for i in List:
    Count_List[i-1] = List[i]

for i in range(0,len(Count_List)):
    print(Count_List[i])
### BUGGY CODE ###

import collections
N = int(input())
A = []
for i in range(N):
    s = sorted(input())
    A.append(str(s))
cnt = 0
for i in set(A):
    k = collections.Counter(A)[i]
    cnt += k*(k-1)//2
print(cnt)

### FIXED CODE ###

import collections
N = int(input())
A = []
for i in range(N):
    s = sorted(input())
    A.append(str(s))
B = collections.Counter(A)
print(sum(i*(i-1)//2 for i in B.values()))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2*100000)
n, m = map(int,input().split())
mark = [-2] * (n-1)
dist = [0] * (n-1)
path = [[] for _ in range(n-1)]
path0 = []

def search(i):
    d = dist[i]
    p = []
    for p in path[i]:
        if dist[p] > d + 1 or dist[p] == 0:
            dist[p] = d + 1
            mark[p] = i
            search(p)

for _ in range(m):
    a, b = map(lambda x: int(x)-2, input().split())
    if a == -1:
        path0.append(b)
        dist[b] = 1
        mark[b] = -1
    elif b == -1:
        path0.append(a)
        dist[a] = 1
        mark[a] = -1
    else:
        path[a].append(b)
        path[b].append(a)

for p in path0:
    search(p)

if mark.count(-2) > 0:
    print("No")
else:
    print("Yes")
    for i in mark: print(i+2)


### FIXED CODE ###

import sys
sys.setrecursionlimit(2*100000)
n, m = map(int,input().split())
mark = [-2] * (n-1)
dist = [0] * (n-1)
path = [[] for _ in range(n-1)]
path0 = []

for _ in range(m):
    a, b = map(lambda x: int(x)-2, input().split())
    if a == -1:
        path0.append(b)
        dist[b] = 1
        mark[b] = -1
    elif b == -1:
        path0.append(a)
        dist[a] = 1
        mark[a] = -1
    else:
        path[a].append(b)
        path[b].append(a)

while len(path0) > 0:
    i = path0.pop(0)
    d = dist[i]
    for p in path[i]:
        if dist[p] > d + 1 or dist[p] == 0:
            dist[p] = d + 1
            mark[p] = i
            path0.append(p)

print("Yes")
for i in mark: print(i+2)
### BUGGY CODE ###

import copy

def funcabs(a,b):
    if a>=b: ret = a-b
    else: ret = b-a
    return ret

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

for i in range(1,N+1):
    ans = 0
    B = copy.deepcopy(A)
    del B[i]
    for j in range(1,N+1):
        ans += funcabs(B[j],B[j-1])
    print(ans)

### FIXED CODE ###

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

S = 0
for i in range(len(A)-1):
    S+=abs(A[i+1]-A[i])
    
for i in range(1,N+1):
    ans = S + abs(A[i+1]-A[i-1]) - abs(A[i+1]-A[i]) - abs(A[i]-A[i-1])
    print(ans)
### BUGGY CODE ###

N = int(input())
P = 10**9 + 7

power = 1

for i in range(1,N+1):
 power *= i

print(power % P)

### FIXED CODE ###

N = int(input())
P = 10**9 + 7

power = 1

for i in range(1,N+1):
 power = (i * power % P)

print(power)
### BUGGY CODE ###

N, K = map(int, input().split())
H = [int(h) for h in input().split()]

if len(H) <= K:
  print(0)
  exit()
  
for i in range(K):
  H.remove(max(H))
print(sum(H))

### FIXED CODE ###

N, K = map(int, input().split())
H = [int(h) for h in input().split()]
H = list(sorted(H, reverse = True))

if len(H) <= K:
  print(0)
else:
  del H[0:K]
  print(sum(H))
### BUGGY CODE ###


#math
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)

def gcd3(lis): #最大公約数(3over)
  ans = lis[0]
  for li in lis:
    ans = gcd(ans,li)
  return ans
    
n = int(input())

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

maxgcd = 0
for i in range(n):
  nums = [a[j] for j in range(n) if j!=i]
  #print(nums)
  tmp = gcd3(nums)
  if maxgcd<tmp:
    maxgcd=tmp
    
print(maxgcd)




### FIXED CODE ###


import sys

def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))


if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)


tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)

for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)
### BUGGY CODE ###

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


l = 0
r = 10 ** 20
while r - l > 1:
    m = (r + l) // 2
    N = m
    for a in A:
        N -= N % a

    if N > 2:
        r = m
    else:
        l = m
upper = l


l = 0
r = 10 ** 20
while r - l > 1:
    m = (r + l) // 2
    N = m
    for a in A:
        N -= N % a

    if N < 2:
        l = m
    else:
        r = m
lower = r

if lower > upper:
    print(-1)
else:
    print(lower, upper)


### FIXED CODE ###

K = int(input())
A = tuple(map(int, input().split()))

l, r = 1, 10 ** 18
while r - l > 1:
    m = (l + r) // 2
    M = m
    for a in A:
        M = (M // a) * a

    if M <= 2:
        l = m
    else:
        r = m
ans_max = l

l, r = 1, 10 ** 18
while r - l > 1:
    m = (l + r) // 2
    M = m
    for a in A:
        M = (M // a) * a

    if M >= 2:
        r = m
    else:
        l = m
ans_min = r

if ans_min > ans_max:
    print(-1)
else:
    print(ans_min, ans_max)
### BUGGY CODE ###

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

N = len(s)

d = dict()
for i in range(N):
    for j in range(i, N):
        sub = s[i:j+1]
        if d.get(sub) == None:
            d[sub] = 1

d2 = sorted(d.items())
print(d2[K-1][0])


### FIXED CODE ###

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

N = len(s)

d = dict()
for i in range(N):
    for j in range(i, min(N, i+K)):
        sub = s[i:j+1]
        if d.get(sub) == None:
            d[sub] = 1

d2 = sorted(d.items())
print(d2[K-1][0])
### BUGGY CODE ###

from heapq import heappush,heappop
from sys import setrecursionlimit
setrecursionlimit(10**6)
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    u,v=u-1,v-1
    table[u].append([a,v])
    table[v].append([a,u])
    rtable[u].append([b,v])
    rtable[v].append([b,u])
mod=pow(10,15)
def dijk(s,table):
    dij=[]
    heappush(dij,[0,s])
    val=[mod]*N
    val[s]=0
    while len(dij)>0:
        q,x=heappop(dij)
        if val[x]<q:
            continue
        for d,y in table[x]:
            if val[y]>val[x]+d:
                val[y]=val[x]+d
                heappush(dij,[val[y],y])
    return val
val=dijk(s-1,table)
rval=dijk(t-1,rtable)
score=[0]*N
for i in range(N):
    score[i]=mod-(val[i]+rval[i])
amax=[mod]*N
amax[-1]=score[-1]
for i in range(N-2,-1,-1):
    amax[i]=max(amax[i+1],score[i])
for i in range(N):
    print(amax[i])

### FIXED CODE ###

from heapq import heappush,heappop
from collections import deque
N,M,s,t=map(int,input().split())
table=[[] for i in range(N)]
rtable=[[] for i in range(N)]
for i in range(M):
    u,v,a,b=map(int,input().split())
    table[u-1].append([a,v-1])
    table[v-1].append([a,u-1])
    rtable[u-1].append([b,v-1])
    rtable[v-1].append([b,u-1])
dij=[]
heappush(dij,[0,s-1])
val=[10**16]*N
val[s-1]=0
while dij:
    q,x=heappop(dij)
    if val[x]<q:
        continue
    for d,y in table[x]:
        if val[y]>val[x]+d:
            val[y]=val[x]+d
            heappush(dij,[val[y],y])
rdij=[]
heappush(rdij,[0,t-1])
rval=[10**16]*N
rval[t-1]=0
while rdij:
    q,x=heappop(rdij)
    if rval[x]<q:
        continue
    for d,y in rtable[x]:
        if rval[y]>rval[x]+d:
            rval[y]=rval[x]+d
            heappush(rdij,[rval[y],y])
ans=deque()
t=val[N-1]+rval[N-1]
mod=pow(10,15)
ans.append(mod-t)
for i in range(N-2,-1,-1):
    t=min(t,val[i]+rval[i])
    ans.appendleft(mod-t)
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]

hc = [0]*h
wc = [0]*w
d={}
for _h, _w in hw:
    hc[_h-1]+=1
    wc[_w-1]+=1
    d[(_h-1,_w-1)]=1
    
maxh = max(hc)
maxw = max(wc)
    
hoge = True
wi = [i for i in range(w) if wc[i]==maxw]
for h in [i for i in range(h) if hc[i]==maxh]:
    for w in wi:
        if (h,w) not in d:
            hoge=False
            
if hoge:
    print(maxh+maxw-1)
else:
    print(maxh+maxw)

### FIXED CODE ###

h,w,m = map(int,input().split())
hw = [list(map(int,input().split())) for _ in range(m)]

hc = [0]*h
wc = [0]*w
d={}
for _h, _w in hw:
    hc[_h-1]+=1
    wc[_w-1]+=1
    d[(_h-1,_w-1)]=1
    
maxh = max(hc)
maxw = max(wc)
    
        
hoge = True
wi = [i for i in range(w) if wc[i]==maxw]
for h in [i for i in range(h) if hc[i]==maxh]:
    for w in wi:
        if (h,w) not in d:
            hoge=False
            break
            
if hoge:
    print(maxh+maxw-1)
else:
    print(maxh+maxw)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque


class LinkedGraph:
    def __init__(self, n):
        self.n = n
        self.ll = [[] for _ in range(self.n)]

    def link(self, u, v, direction=False):
        self.ll[u].append(v)
        if not direction:
            self.ll[v].append(u)

    def check(self, start, goal):
        states = [0] * self.n
        queue = deque([start])

        while queue:
            u = queue.popleft()
            if states[u]:
                continue
            else:
                states[u] = 1

            for v in self.ll[u]:
                if v == goal:
                    print('yes')
                    return
                queue.append(v)

        else:
            print('no')
            return


if __name__ == '__main__':
    n, m = map(int, input().split())
    g = LinkedGraph(n)

    for _ in range(m):
        u, v = map(int, input().split())
        g.link(u, v)

    q = int(input())
    for _ in range(q):
        u, v = map(int, input().split())
        g.check(u, v)



### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)


class LinkedList:
    def __init__(self, n):
        self.n = n
        self.ll = [[] for _ in range(self.n)]

    def link(self, u, v, direction=False):
        self.ll[u].append(v)
        if not direction:
            self.ll[v].append(u)

    def dfs(self):
        self.cc = [None] * self.n

        color = 1
        for u in range(self.n):
            if not self.cc[u]:
                self.dfs_visit(u, color)
                color += 1

    def dfs_visit(self, u, color):
        self.cc[u] = color
        for v in self.ll[u]:
            if not self.cc[v]:
                self.dfs_visit(v, color)

    def check(self, u, v):
        if self.cc[u] == self.cc[v]:
            print('yes')
        else:
            print('no')


if __name__ == '__main__':
    n, m = map(int, input().split())
    ll = LinkedList(n)

    for _ in range(m):
        u, v = map(int, input().split())
        ll.link(u, v)
    ll.dfs()

    q = int(input())
    for _ in range(q):
        u, v = map(int, input().split())
        ll.check(u, v)
### BUGGY CODE ###

S=input()
count=0
for i in range(len(S)):
    if S[i]=="W":
        count+=S[:i].count("B")
print(count)

### FIXED CODE ###

S=input()
count=0
ans=0
for i in range(len(S)):
    if S[i]=="W":
        ans+=count
    else:
        count+=1
print(ans)
### BUGGY CODE ###

from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# from operator import xor
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    L=list(map(int,input().split()))

    cnt=0
    for i in combinations(L,3):
        if sum(i)-2*i[0]>0 and sum(i) - 2 * i[1] > 0 and sum(i)-2*i[2]>0:
            cnt+=1
            
    print(cnt)

resolve()

### FIXED CODE ###

import bisect
# from collections import Counter, deque
# from copy import copy, deepcopy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# from operator import xor
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    N=int(input())
    L=sorted(list(map(int,input().split())))
    cnt=0
    for i in range(N-2):
        for j in range(i+1,N-1):

            val=bisect.bisect_left(L,L[i]+L[j])
            cnt+=val-j-1

    print(cnt)

resolve()
### BUGGY CODE ###

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)

maxA_len = len(bin(maxA)[2:])
num0_each_digit = [0 for _ in range(maxA_len)]
num1_each_digit = [0 for _ in range(maxA_len)]

for i in range(N):
    for i_bit, bit in enumerate(bin(A[i])[2:].zfill(maxA_len)):
        if bit == '0':
            num0_each_digit[i_bit] += 1
            num0_each_digit[i_bit] %= MOD
        else:
            num1_each_digit[i_bit] += 1
            num1_each_digit[i_bit] %= MOD
ans = 0
for i in range(maxA_len):
    ans += (num0_each_digit[i] * num1_each_digit[i] * (2 ** (maxA_len - i - 1))) % MOD

print(ans % MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)

maxA_len = len(bin(maxA)[2:])
num0_each_digit = [0 for _ in range(maxA_len)]
num1_each_digit = [0 for _ in range(maxA_len)]

for i in range(N):
    for i_bit, bit in enumerate(bin(A[i])[2:].zfill(maxA_len)):
        if bit == '0':
            num0_each_digit[i_bit] += 1
            num0_each_digit[i_bit] %= MOD
        else:
            num1_each_digit[i_bit] += 1
            num1_each_digit[i_bit] %= MOD
ans = 0
for i in range(maxA_len):
    factor = (2 ** (maxA_len - i - 1)) % MOD
    ans += (num0_each_digit[i] * num1_each_digit[i] * factor) % MOD

print(ans % MOD)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

offsets = [(1, 0), (-1, 0), (0, 1), (0, -1)]
graph = [[float('inf')] * W for _ in range(H)]
deq = deque()

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            graph[i][j] = 0
            deq.append((i, j))

while deq:
    x, y = deq.popleft()
    for i, j in offsets:
        if (not 0 <= x + i < H) or (not 0 <= y + j < W):
            continue

        if graph[x + i][y + j] < float('inf'):
            continue

        if grid[x + i][y + j] == '#':
            continue
            
        graph[x + i][y + j] = graph[x][y] + 1
        deq.append((x + i, y + j))
        
print(max(max(v) for v in graph))

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

offsets = [(1, 0), (-1, 0), (0, 1), (0, -1)]
graph = [[float('inf')] * W for _ in range(H)]
deq = deque()

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            graph[i][j] = 0
            deq.append((i, j))

while deq:
    x, y = deq.popleft()
        
    for i, j in offsets:
        if (not 0 <= x + i < H) or (not 0 <= y + j < W):
            continue

        if graph[x + i][y + j] < float('inf'):
            continue

        if grid[x + i][y + j] == '#':
            continue
            
        graph[x + i][y + j] = graph[x][y] + 1
        deq.append((x + i, y + j))
        
print(max(max(v) for v in graph))
### BUGGY CODE ###

import sys
from collections import deque

def main():

    input = sys.stdin.readline

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

    A = [0] * M
    B = [0] * M

    friend_list = [ set() for _ in range(N)]
    friend_list_len = 0

    for i in range(M):
        A[i],B[i] = map(int,input().split())

    for i in range(M):
        for j in range(friend_list_len):
            flag = False
            if A[i] in friend_list[j]:
                friend_list[j].add(B[i])
                flag = True
            if B[i] in friend_list[j]:
                friend_list[j].add(A[i])
                flag = True
            if flag:
                break                
        else:
            friend_list[friend_list_len].add(A[i])
            friend_list[friend_list_len].add(B[i])
            friend_list_len += 1

    ans = 1
    for i in range(friend_list_len):
        ans = max(ans,len(friend_list[i]))

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def main():

    input = sys.stdin.readline

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

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

    UF = UnionFind(N)

    for i in range(M):
        A,B = AB[i]

        A = A - 1
        B = B - 1

        UF.union(A,B)


    ans = 1
    for i in range(N):
        ans = max(ans,UF.size(i))

    print(ans)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

import bisect

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

A.sort()
B.sort()
C.sort()

ans = 0
for i in range(N):
    a=A[i]
    nibanme = bisect.bisect_right(B,a)
    for j in range(nibanme,N):
        b=B[j]
        sanbanme = bisect.bisect_right(C,b)
        ans += N-sanbanme

print(ans)


### FIXED CODE ###

import bisect

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

A.sort()
B.sort()
C.sort()

ans = 0
for i in range(N):
    b=B[i]
    a=bisect.bisect_left(A,b)
    c=bisect.bisect_right(C,b)
    ans+= a*(N-c)

print(ans)
### 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()))
A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
cor = []
for i in range(X):
    for j in range(Y):
        cor.append(A[i]+B[j])

cor.sort(reverse = True)
cor = cor[:min(K,X*Y)]
anslist = []
for i in range(min(K,X*Y)):
    for j in range(Z):
        anslist.append(C[j]+cor[i])

anslist.sort(reverse = True)
for i in range(K):
    print(anslist[i])

### FIXED CODE ###

from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
Mod = 1000000007




def main(): #startline--------------------------------------------
    X,Y,Z,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort(reverse = True)
    A = A[:min(K,X)]
    B = list(map(int,input().split()))
    B.sort(reverse = True)
    B = B[:min(K,X)]
    C = list(map(int,input().split()))
    C.sort(reverse = True)
    C = C[:min(K,X)]
    Pre = []
    for i in range(min(X,K)):
        for j in range(min(Y,K)):
            Pre.append(A[i]+B[j])
    Pre.sort(reverse = True)
    Pre = Pre[:K]
    ans = []
    for i in range(min(Z,K)):
        for j in Pre:
            ans.append(j+C[i])
    ans.sort(reverse = True)
    for i in range(K):
        print(ans[i])



if __name__ == "__main__":
    main() #endline===============================================





def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
### BUGGY CODE ###

n = int(input())
a = list(int(input()) for _ in range(n))

num = max(a)
for i in range(n):
    if a[i] < num:
        print(num)
    else:
        b = a.copy()
        int(b.pop(i))
        print(max(b))

### FIXED CODE ###

n = int(input())
a = list(int(input()) for _ in range(n))

max_list = sorted(a,reverse=True)[:2]
num = max_list[0]
num2 = max_list[1]

for i in range(n):
    if a[i] < num:
        print(num)
    else:
        print(num2)
### BUGGY CODE ###

def solve():
  N = int(input())
  AA = list(map(int,input().split()))

  ans = 0
  for a in AA:
    ans += a
  ans = ans % (10**9+7)
  ans = ans**2
  ans = ans % (10**9+7)
  for a in AA:
    ans -= a**2
    while ans<0:
      ans += 10**9+7
  ans = ans % (10**9+7)
  print(int(ans/2))
solve()

### FIXED CODE ###

def solve():
  N = int(input())
  AA = list(map(int,input().split()))
 
  ans = 0
  for a in AA:
    ans += a
  ans = ans**2
  for a in AA:
    ans -= a**2
  ans = ans//2
  print(ans%(10**9+7))
solve()