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

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

def main():
    scores = []
    score = 1
    for i in range(k-1, -1, -1):
        score *= a[i]

    scores.append(score)
    scores_append = scores.append

    for j in range(k, n):
        score_before = scores[-1]
        score = score_before * a[j] / a[j-k]
        scores_append(score)
        if score > score_before:
            print('Yes')
        else:
            print('No')

            
if __name__ == '__main__':
    main()    

### FIXED CODE ###

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

for i in range(k, n):
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()

    for n in range(N):
        print(A.count(n+1))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    ret = [0]*N
    for a in A:
        ret[a-1] += 1
    print(*ret, sep="\n")


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

import itertools
n = int(input())
L = list(map(int,input().split()))
cnt = 0
for i in itertools.combinations(L, 3):
  if i[0] < i[1]+i[2] and i[1] < i[0]+i[2] and i[2] < i[0]+i[1]:
    cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
L = sorted(((map(int,input().split()))))
#print(L)
cnt = 0
for i in range(n):
  for j in range(i+1,n):
    num = L[i] + L[j]
    b = bisect.bisect_left(L, num)
    #print(L[i], L[j], b, cnt)
    if b-1 > j:
      cnt += b-1-j
print(cnt)
### BUGGY CODE ###

N = int(input())
S = input()

count = {"R": 0, "G": 0, "B": 0}
char2num = {"R": 1, "G": 10, "B": 100}
count_list = []

for char in S[::-1]:
    count[char] += 1
    count_list.append((count["R"], count["G"], count["B"]))
count_list = count_list[::-1]
        

ans = 0
for i in range(N-2):
    one = char2num[S[i]]
    for j in range(i+1, N-1):
        two = char2num[S[j]]
        if one != two:
            tmp = j+(j-i) < N
            if one+two == 11:
                if tmp and S[j+(j-i)] == "B":
                    ans += count_list[j][2] - 1
                else:
                    ans += count_list[j][2]
                    
            if one+two == 101:
                if tmp and S[j+(j-i)] == "G":
                    ans += count_list[j][1] - 1
                else:
                    ans += count_list[j][1]
                    
            if one+two == 110:
                if tmp and S[j+(j-i)] == "R":
                    ans += count_list[j][0] - 1
                else:
                    ans += count_list[j][0]
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

count = {"R": 0, "G": 0, "B": 0}
char2num = {"R": 1, "G": 10, "B": 100}
count_list = []

for char in S[::-1]:
    count[char] += 1
    count_list.append((count["R"], count["G"], count["B"]))
count_list = count_list[::-1]
        

ans = 0
for i in range(N-2):
    one = char2num[S[i]]
    for j in range(i+1, N-1):
        two = char2num[S[j]]
        if one != two:
            tmp = j+(j-i) < N
            if one+two == 11:
                if tmp and S[j+(j-i)] == "B":
                    ans += count_list[j][2] - 1
                else:
                    ans += count_list[j][2]
                    
            if one+two == 101:
                if tmp and S[j+(j-i)] == "G":
                    ans += count_list[j][1] - 1
                else:
                    ans += count_list[j][1]
                    
            if one+two == 110:
                if tmp and S[j+(j-i)] == "R":
                    ans += count_list[j][0] - 1
                else:
                    ans += count_list[j][0]
print(ans)
### BUGGY CODE ###

A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]
inf = 10 ** 18

s.insert(0, -inf)
s.insert(A + 1, inf)
t.insert(0, -inf)
t.insert(B + 1, inf)

sthome = []
for si in s: sthome.append((si, 's'))
for ti in t: sthome.append((ti, 't'))
sthome.sort(key=lambda x: x[0])

st = []
home = []
for sti, homei in sthome:
    st.append(sti)
    home.append(homei)
# print("#", st[2:len(st)-2], home)

    
def binsearch_l(seq, l, r, tar):
    if r - l < 2: return l
    #
    m = l + (r - l) // 2
    # print("##", l, r, (m, seq[m]), tar)
    if seq[m] <= tar:
        return binsearch_l(seq, m, r, tar)
    else:
        return binsearch_l(seq, l, m, tar)

for x_tmp in x:
    i_l = binsearch_l(st, 0, A + B + 4, x_tmp)
    #
    ans = inf
    #
    for i_tmp in (i_l, i_l + 1):
        if st[i_tmp] in (-inf, inf): continue
        ans_tmp = inf
        if home[i_tmp] == 's':
            j_l = binsearch_l(t, 0, B + 2, st[i_tmp])
            for j_tmp in (j_l, j_l + 1):
                if t[j_tmp] in (-inf, inf): continue
                ans_tmp_tmp = abs(x_tmp - st[i_tmp]) + abs(t[j_tmp] - st[i_tmp])
                # print("##", (i_tmp, j_tmp), x_tmp, st[i_tmp], t[j_tmp], ans_tmp_tmp)
                if ans_tmp > ans_tmp_tmp:
                    ans_tmp = ans_tmp_tmp
        else:
            j_l = binsearch_l(s, 0, A + 2, st[i_tmp])
            for j_tmp in (j_l, j_l + 1):
                if s[j_tmp] in (-inf, inf): continue
                ans_tmp_tmp = abs(x_tmp - st[i_tmp]) + abs(s[j_tmp] - st[i_tmp])
                # print("##", (i_tmp, j_tmp), x_tmp, st[i_tmp], s[j_tmp], ans_tmp_tmp)
                if ans_tmp > ans_tmp_tmp:
                    ans_tmp = ans_tmp_tmp
        if ans > ans_tmp:
            ans = ans_tmp
    #
    print(ans)

### FIXED CODE ###

import sys, bisect
input = sys.stdin.readline
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]
inf = 10 ** 18

s = [-inf] + s + [inf]
t = [-inf] + t + [inf]

ans_Q = [None] * Q
i_last = j_last = 0
for idx, x_tmp in sorted(enumerate(x), key=lambda x: x[1]):
    i_l = max(0, bisect.bisect_left(s, x_tmp, lo=i_last) - 1)
    j_l = max(0, bisect.bisect_left(t, x_tmp, lo=j_last) - 1)
    # print("#", x_tmp, (i_l, s[i_l]), (j_l, t[j_l]))
    #
    ans = inf
    for i, j in ((i_l, j_l), (i_l + 1, j_l), (i_l, j_l + 1), (i_l + 1, j_l + 1)):
        if i < 1 or A < i: continue
        if j < 1 or B < j: continue
        ans_tmp_s = abs(x_tmp - s[i]) + abs(s[i] - t[j])
        ans_tmp_t = abs(x_tmp - t[j]) + abs(s[i] - t[j])
        ans_tmp = min(ans_tmp_s, ans_tmp_t)
        # print("#", x_tmp, s[i], t[j], ans_tmp)
        if ans > ans_tmp:
            ans = ans_tmp
    #
    i_last, j_last = i_l, j_l
    ans_Q[idx] = ans

for ansi in ans_Q: print(ansi)
### BUGGY CODE ###

n,k=map(int,input().split())
array=[]
for i in range(n):
    a,b=map(int,input().split())
    for j in range(b):
        array.append(a)
ans=sorted(array)
print(ans[k-1])

### FIXED CODE ###

n,k=map(int,input().split())
array=[]
for i in range(n):
    array.append(list(map(int,input().split())))
array.sort(key=lambda x:x[0])
q=True
count=0
i=0
while q:
    count +=array[i][1]
    if k<=count:
        print(array[i][0])
        exit()
    else:
        i +=1
### BUGGY CODE ###

from collections import defaultdict

d = defaultdict(int)

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

operations = []

for i in range(q):
    temp = input().split(" ")
    operations.append((int(temp[0]), int(temp[1])))


# n = 5
# a = [1, 2, 3, 4, 5]
# q = 3

# operations = [
#     (1, 2),
#     (2, 3),
#     (3, 4)
# ]

for hoge in a:
    d[hoge] += 1


for op in operations:
    target, goto = op

    d[goto] += d[target]

    try:
        del d[target]
        sum = 0
        for key, value in d.items():
            sum += key * value

        print(sum)

    except:
        sum = 0
        for key, value in d.items():
            sum += key * value

        print(sum)     




### FIXED CODE ###

from collections import defaultdict

d = defaultdict(int)

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

operations = []

for i in range(q):
    temp = input().split(" ")
    operations.append((int(temp[0]), int(temp[1])))

for hoge in a:
    d[hoge] += 1

initial_sum = 0
for key, value in d.items():
    initial_sum += key * value

for op in operations:
    target, goto = op

    before = goto * d[goto] + target * d[target]
    d[goto] += d[target]
    d[target] = 0

    after = goto * d[goto]
    diff = after - before
    
    initial_sum += diff
    print(initial_sum)
### BUGGY CODE ###

"""
dp[i][j] : i番目において、(表-裏)+N=j
dp[i+1][j+1] : dp[i][j] * (表)
dp[i+1][j-1] : dp[i][j] * (裏)
"""
N = int(input())
ps = list(map(float, input().split()))

dp = [[0]*(2*N+1) for i in range(N+1)]
dp[0][N] = 1
for i,p in enumerate(ps):
    for j in range(2*N):
        dp[i+1][j-1] += dp[i][j] * (1-p)
        dp[i+1][j+1] += dp[i][j] * p
    # print(dp[i+1])
print(sum(dp[N][N:]))

### FIXED CODE ###

"""
dp[i][j] : i番目において、(表-裏)+N=j
dp[i+1][j+1] : dp[i][j] * (表)
dp[i+1][j-1] : dp[i][j] * (裏)
"""
N = int(input())
ps = list(map(float, input().split()))

dp = [[0]*(2*N+1) for i in range(N+1)]
dp[0][N] = 1
for i,p in enumerate(ps):
    for j in range(2*N):
        dp[i+1][j-1] += dp[i][j] * (1-p)
        dp[i+1][j+1] += dp[i][j] * p
    # print(dp[i+1])
print(sum(dp[N][N:]))
### BUGGY CODE ###

import sys
import collections
n = int(input())
a = collections.deque()
for i in range(n):
    k = collections.deque([int(x) for x in input().split()])
    a.append(k)
ans = 0
key = 0
while a:
    s = 1
    todaylist = []
    for i in range(n):
        if i+1 in todaylist:
            continue
        if a[i]:
            if a[i][0] in todaylist:
                continue
            b = a[i][0]-1
            if a[b]:
                if a[b][0] == i+1:
                    a[i].popleft()
                    a[b].popleft()
                    todaylist.append(i+1)
                    todaylist.append(b+1)
                    s = 0
    ans += 1
    key += 1
    if s:
        print(-1)
        sys.exit()
    if key >= n-1 and not any(a):
        break
print(ans)

### FIXED CODE ###

import sys
from copy import deepcopy as copy

def main():
    input = sys.stdin.readline
    n = int(input())
    a = [None]*n
    for i in range(n):
        a[i] = [int(x)-1 for x in input().split()]
    
    index = [0]*n
    search = [int(x) for x in range(n)]
    ans = 0
    while True:
        already = set()
        judge = True
        sub = []
        for key in search:
            if index[key] == n-1:
                continue
            key2 = a[key][index[key]]
            if index[key2] == n-1:
                continue
            if key != a[key2][index[key2]]:
                continue
            if key in already or key2 in already:
                continue
            already.add(key)
            already.add(key2)
            index[key] += 1
            index[key2] += 1
            sub.append(key)
            sub.append(key2)
            judge = False
        if judge:
            break
        ans += 1
        search = copy(sub)
        
    for value in index:
        if value != n-1:
            print(-1)
            sys.exit()
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(M):
    index = A.index(max(A))
    A[index] = A[index] // 2
print(sum(A))


### FIXED CODE ###

import math
import heapq

N, M = map(int, input().split())
tempA = list(map(int, input().split()))
A = []
for a in tempA:
    heapq.heappush(A, a * - 1)
for i in range(M):
    minNum = heapq.heappop(A)
    heapq.heappush(A, (minNum * -1 // 2) * - 1)
print(sum(A) * -1)
### BUGGY CODE ###

def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    grid = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            grid[i][j] = abs(A[i][j] - B[i][j])

    dp = [[set() for _ in range(W)] for _ in range(H)]
    dp[0][0].add(grid[0][0])

    for i in range(H):
        for j in range(W):
            for k in dp[i][j]:
                if i < H - 1:
                    nk = grid[i + 1][j]
                    dp[i + 1][j].add(k + nk)
                    dp[i + 1][j].add(abs(k - nk))
                if j < W - 1:
                    nk = grid[i][j + 1]
                    dp[i][j + 1].add(k + nk)
                    dp[i][j + 1].add(abs(k - nk))

    print(min(dp[-1][-1]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

H, W = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
Diff = [[0] * (W + 1) for _ in range(H + 1)]
M = 0
for i in range(H):
    for j in range(W):
        m = abs(A[i][j] - B[i][j])
        Diff[i][j] = m
        M += m

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] |= (1 << Diff[i][j])

for i in range(0, H):
    for j in range(0, W):
        here = dp[i][j]
        s = Diff[i][j]
        ni = 0
        nj = 0
        ni |= (here << s)
        nj |= (here << s)
        ni |= (here >> s)
        nj |= (here >> s)
        ex = 0
        for k in range(1, s + 1):
            if (here >> k) & 1:
                ex |= (1 << (s - k))
        ni |= ex
        nj |= ex
        dp[i + 1][j] |= ni
        dp[i][j + 1] |= nj

a = dp[H - 1][W - 1]
ans = 0
for k in range(M + 1):
    if (a >> k) & 1:
        ans = k
        break

print(k)
### BUGGY CODE ###

def main():
    N, MA, MB = list(map(int, input().split()))
    chemicals = [list(map(int, input().split())) for _ in range(N)]
    INF_COST = 1 + sum([chemical[2] for chemical in chemicals])
    MAX_A, MAX_B = 400, 400
    # dp[a][b]: 物質Aをaグラム、物質Bをbグラム入手するのに必要な最小コスト
    #           状態数は400 * 400 = 160000
    #           薬品の個数は40個
    #           → 更新ステップ数は 160000 * 40 = 6400000 = 6.4 * (10**6)
    dp = [[INF_COST for _ in range(1 + MAX_B)] for _ in range(1 + MAX_A)]
    dp[0][0] = 0
    for chemical in chemicals:
        da, db, dc = chemical
        for a in range(MAX_A, -1, -1):
            if a + da > MAX_A:
                continue
            for b in range(MAX_B, -1, -1):
                if b + db > MAX_B:
                    continue
                dp[a + da][b + db] = min(dp[a + da][b + db], dc + dp[a][b])
    ans = INF_COST
    scale = 1
    while scale * MA <= MAX_A and scale * MB <= MAX_B:
        ans = min(ans, dp[scale * MA][scale * MB])
        scale += 1
    if ans == INF_COST:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, MA, MB = list(map(int, input().split()))
    chemicals = [list(map(int, input().split())) for _ in range(N)]
    INF_COST = 1 + sum([chemical[2] for chemical in chemicals])
    MAX_A, MAX_B = 400, 400
    # dp[a][b]: 物質Aをaグラム、物質Bをbグラム入手するのに必要な最小コスト
    #           状態数は400 * 400 = 160000
    #           薬品の個数は40個
    #           → 更新ステップ数は 160000 * 40 = 6400000 = 6.4 * (10**6)
    dp = [[INF_COST for _ in range(1 + MAX_B)] for _ in range(1 + MAX_A)]
    dp[0][0] = 0
    for chemical in chemicals:
        da, db, dc = chemical
        for a in range(MAX_A, -1, -1):
            if a + da > MAX_A:
                continue
            for b in range(MAX_B, -1, -1):
                if b + db > MAX_B:
                    continue
                dp[a + da][b + db] = min(dp[a + da][b + db], dc + dp[a][b])
    ans = INF_COST
    scale = 1
    while scale * MA <= MAX_A and scale * MB <= MAX_B:
        ans = min(ans, dp[scale * MA][scale * MB])
        scale += 1
    if ans == INF_COST:
        print(-1)
    else:
        print(ans)


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

#!/usr/bin/env python3

H, W, M = map(int, input().split())
tate = [0] * H
yoko = [0] * W
S = []

for i in range(M):
    h, w = map(int, input().split())
    tate[h-1] += 1
    yoko[w-1] += 1
    S.append([h-1, w-1])


yoko_max = max(yoko)
yoko_index = []
tate_max = max(tate)
tate_index = []

for i in range(len(yoko)):
    if yoko[i] == yoko_max: yoko_index.append(i)

for i in range(len(tate)):
    if tate[i] == tate_max: tate_index.append(i)

flag = True

for i in range(len(yoko_index)):
    for j in range(len(tate_index)):
        if [tate_index[j], yoko_index[i]] in S:
            continue
        else:
            print(tate_max + yoko_max)
            exit()


print(tate_max + yoko_max - 1)


### FIXED CODE ###

#!/usr/bin/env python3
import collections

H, W, M = map(int, input().split())
tate = []
yoko = []
S = set()

for i in range(M):
    h, w = map(int, input().split())
    tate.append(h-1)
    yoko.append(w-1)
    S.add((h-1, w-1))

tate = collections.Counter(tate)
yoko = collections.Counter(yoko)
yoko_max = yoko.most_common()[0][1]
yoko_index = []
tate_max = tate.most_common()[0][1]
tate_index = []

for k, v in yoko.most_common():
    if v == yoko_max: yoko_index.append(k)
    else: break

for k, v in tate.most_common():
    if v == tate_max: tate_index.append(k)
    else: break

for i in yoko_index:
    for j in tate_index:
        if (j, i) in S:
            continue
        else:
            print(tate_max + yoko_max)
            exit()


print(tate_max + yoko_max - 1)
### BUGGY CODE ###

##C - Step
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N):
    if A:
        Idx = A.index(max(A))
        ans += max(A)*(len(A) - Idx) - sum(A[Idx::])
        del A[Idx::]
    else:
        break
print(ans)

### FIXED CODE ###

##C - Step(TLE)
N = int(input())
A = list(map(int,input().split()))
ans = 0
maxi = 0
for i in A:
    ans += max(0,maxi-i)
    maxi = max(maxi,i)
print(ans)
### BUGGY CODE ###

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    ans = 0
    for ai in range(N-2):
        a = L[ai]
        for bi in range(ai+1,N-1):
            b = L[bi]
            cleft = max((a - b), (b - a))
            cright = a + b
            left_index = bisect.bisect_left(L[bi+1:],cleft)
            right_index = bisect.bisect_left(L[bi+1:],cright)
            if left_index == right_index:
                if L[bi+1+left_index] < cright:
                    ans += 1
            else:
                ans += (right_index - left_index)
    print(ans)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))
    L.sort()
    ans = 0
    for ai in range(N-2):
        a = L[ai]
        for bi in range(ai+1,N-1):
            b = L[bi]
            cmax = a + b
            m_index = bisect.bisect_left(L,cmax)
            ans += max(m_index - bi - 1, 0)

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

import math


def get_group_num(ele):
    for i in range(len(group_list)):
        if ele in group_list[i]:
            return i
    raise Exception('could not find ele in any groups')


N, M = list(map(int, input().split()))
bridge_list = list()
for _ in range(M):
    bridge_list.append(list(map(int, input().split())))

answer_list = [math.factorial(N) // math.factorial(2) // math.factorial(N - 2)]
group_list = [[i] for i in range(1, N + 1)]

for bridge_list in bridge_list[:0:-1]:
    a = bridge_list[0]
    b = bridge_list[1]
    a_gid = get_group_num(a)
    b_gid = get_group_num(b)
    if a_gid != b_gid:
        answer_list.append(answer_list[-1] - len(group_list[a_gid]) * len(group_list[b_gid]))
        next_gid = min(a_gid, b_gid)
        old_gid = max(a_gid, b_gid)
        group_list[next_gid] += group_list[old_gid]
        group_list[old_gid] = []
    else:
        answer_list.append(answer_list[-1])

for answer in answer_list[::-1]:
    print(answer)


### FIXED CODE ###

import math


def find_root(ele):
    root = node_list[ele]['root']
    if root is not None:
        return find_root(root)
    return ele


N, M = list(map(int, input().split()))
bridge_list = list()
for _ in range(M):
    bridge_list.append(list(map(int, input().split())))

answer_list = [math.factorial(N) // math.factorial(2) // math.factorial(N - 2)]
node_list = [{'root': None, 'child_count': 0} for i in range(N)]

for bridge_list in bridge_list[:0:-1]:
    a = bridge_list[0] - 1
    b = bridge_list[1] - 1
    a_root = find_root(a)
    b_root = find_root(b)
    if a_root != b_root:
        answer_list.append(answer_list[-1] - (node_list[a_root]['child_count'] + 1) * (node_list[b_root]['child_count'] + 1))
        next_root = min(a_root, b_root)
        old_root = max(a_root, b_root)
        node_list[next_root]['child_count'] += node_list[old_root]['child_count'] + 1
        node_list[old_root]['root'] = next_root
    else:
        answer_list.append(answer_list[-1])

for answer in answer_list[::-1]:
    print(answer)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
MOD = 1000000007

import itertools
c = itertools.combinations(A, 2)
q=0
for v in c:
    q +=v[0]%MOD*v[1]%MOD
print(q%MOD)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
MOD = 1000000007
B=0
tem = sum(A)
for i in range(len(A)):
    tem -= A[i]
    B+= (A[i]%MOD)*(tem%MOD)
print(B%MOD)