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

list1 = list(map(int, input().split()))
n = list1[0]
x = list1[1]
list2 = list(map(int, input().split()))
list2.append(x)
list2.sort()

list3 = []
length = len(list2)
index =1
while index < length:
    list3.append(list2[index]-list2[index-1])
    index+=1

list3.sort()
mimN = list3[0]
ans =0
index2 =1
if len(list3) ==1:
    print(mimN)
else:
    flag2 =0
    for number in list3:
       if number%mimN !=0:
           flag2 =1
    if flag2 ==0:
        print(mimN)
    else:
        while index2<mimN+1:
            flag=0
            for number in list3:
                if number%index2 !=0:
                    flag =1
            if flag ==0:
                ans = index2
            index2+=1
            
        print(ans)

### FIXED CODE ###

list1 = list(map(int, input().split()))
n = list1[0]
x = list1[1]
list2 = list(map(int, input().split()))
list2.append(x)
list2.sort()

list3 = []
list4 = []
length = len(list2)
index =1
while index < length:
    list3.append(list2[index]-list2[index-1])
    index+=1

list3.sort()
mimN = list3[0]
ans =0
index2 =mimN
if len(list3) ==1:
    print(mimN)
else:
    flag2 =0
    for number in list3:
       if number%mimN !=0:
           flag2 =1
    if flag2 ==0:
        print(mimN)
    else:
        while index2>=1:
            flag=0
            for number in list3:
                if number%index2 ==0:
                    flag =1
                else:
                    flag =0
                    break
            if flag ==1:
                ans = index2
                break
            else:
                index2-=1       
        print(ans)
### BUGGY CODE ###

N = int(input())

messages = []
for i in range(N):
    a = int(input())
    message = []
    for j in range(a):
        pair = list(map(int, input().split()))
        message.append(pair)
    messages.append([a, message])


result = 0
for pattern in range(2 ** N):

    confidence = True
    for i in range(N):

        if not ((pattern >> i) & 1):
            continue

        a = messages[i][0]
        message = messages[i][1]
        for j in range(a):
            x, y = message[j][0], message[j][1]

            condition = (pattern >> (x - 1)) & 1
            if condition and y == 0:
                confidence = False

            condition = not ((pattern >> (x - 1)) & 1)
            if condition and y == 1:
                confidence = False

    if confidence:
        count = 0
        for n in range(N):
            if (pattern >> n) & 1:
                count += 1

        result = max(result, count)

print(result)


### FIXED CODE ###

N = int(input())

messages = []
for i in range(N):
    a = int(input())
    message = []
    for j in range(a):
        pair = list(map(int, input().split()))
        message.append(pair)
    messages.append([a, message])


result = 0
for pattern in range(2 ** N):

    confidence = True
    for i in range(N):

        if not ((pattern >> i) & 1):
            continue

        a = messages[i][0]
        message = messages[i][1]
        for j in range(a):
            x, y = message[j][0], message[j][1]

            condition = (pattern >> (x - 1)) & 1
            if condition and y == 0:
                confidence = False

            condition = not ((pattern >> (x - 1)) & 1)
            if condition and y == 1:
                confidence = False

    if confidence:
        count = 0
        for n in range(N):
            if (pattern >> n) & 1:
                count += 1

        result = max(result, count)

print(result)
### BUGGY CODE ###

n = int(input())
G = [[] for i in range(n)]
nodes = {}
root = 0
color_num = 0
keys = []

def get_key(n1, n2):
  if n1 > n2:
    return str(n2) + '-' + str(n1)
  return str(n1) + '-' + str(n2)

for _ in range(n - 1):
  a, b = map(int, input().split())
  keys.append(get_key(a - 1, b - 1))
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  if a in nodes:
    nodes[a] += 1
  else:
    nodes[a] = 1
  if b in nodes:
    nodes[b] += 1
  else:
    nodes[b] = 1
# ex. {1: 1, 2: 4, 3: 1, 4: 2, 5: 2, 6: 2, 7: 1, 8: 1}
# print(nodes)
# print(G)
for i, g in enumerate(G):
  if color_num < len(g):
    root = i
    color_num = len(g)

# [[1], [0, 2, 3, 4], [1], [1, 6], [1, 5], [4, 7], [3], [5]]
# print(root) # 最も多い色を持つノードの番号
print(color_num) # 必要な最小色数
queue = [root]
checked = set()
result = {}

while len(queue) > 0:
  node = queue.pop(0)
  # print(node + 1)
  ks = list(range(color_num))
  for node2 in G[node]:
    key = get_key(node, node2)
    if key in result:
      ks.pop(result[key])
  for node2 in G[node]:
    if node2 not in checked:
      key = get_key(node, node2)
      result[key] = ks.pop(0)
      queue.append(node2)
  checked.add(node)

for k in keys:
  print(result[k] + 1)


### FIXED CODE ###

n = int(input())
G = [[] for i in range(n)]
root = 0
color_num = 0

for i in range(n - 1):
  a, b = map(int, input().split())
  G[a - 1].append((b - 1, i))
  G[b - 1].append((a - 1, i))
  if color_num < len(G[a - 1]):
    root = a - 1
    color_num = len(G[a - 1])
  elif color_num < len(G[b - 1]):
    root = b - 1
    color_num = len(G[b - 1])

# print(G)
# [[1], [0, 2, 3, 4], [1], [1, 6], [1, 5], [4, 7], [3], [5]]
# print(root) # 最も多い色を持つノードの番号
print(color_num)  # 必要な最小色数
queue = [(root, -1)]
checked = set()
answer = [-1] * (n - 1)

while len(queue) > 0:
  node, c = queue.pop(0)
  color = 1
  for node2, index in G[node]:
    if node2 not in checked:
      if color == c:
        color = c + 1
      answer[index] = color
      color += 1
      queue.append((node2, answer[index]))
  checked.add(node)
print('\n'.join(map(str, answer)))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

n,w = MI()
item = []
mem = [[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
	item.append(LI())

def rec(i,w):
	if mem[i][w]!=0:
		return mem[i][w]
	if i == n:
		res = 0
	else:
		if w < item[i][0]:
			res = rec(i+1,w)
		else:
			res = max(rec(i+1,w), rec(i+1,w-item[i][0])+item[i][1])
	mem[i][w]=res
	return res


def main():
	print(rec(0,w))

if __name__ == '__main__':
	main()

### FIXED CODE ###

def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]
 
	for i in range(0,N):
		for j in range(W, item[i][0]-1, -1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[W])
 
solver()
### BUGGY CODE ###

def yakusu(n):
    max_yakusu = int(n**0.5)
    arr = [1]

    while n > 1:
        for i in range(2,max(n+1,max_yakusu+1)):
            if n % i == 0:
                arr.append(i)
                n = int(n/i)
                break
    return arr

A,B = [int(x) for x in input().split()]

A_insu = set(yakusu(A))
B_insu = set(yakusu(B))
print(len(list(A_insu & B_insu)))

### FIXED CODE ###

def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
  
def gcd(x,y):
    if y == 0:
       return x
    else:
       return gcd(y, x % y)
 
A,B = [int(x) for x in input().split()]
koyaku = gcd(A,B)
 
koyaku_insu = list(set(prime_factorize(koyaku)))
 
 
print(len(koyaku_insu))
### BUGGY CODE ###

a,b,c,d = map(int,input().split())

a_b = [i for i in range(a,b+1) if i % c == 0 or i % d == 0]

ans = (b + 1 - a) - len(a_b)
print(ans)

### FIXED CODE ###

a,b,c,d=map(int,input().split())

def gcd(x,y):
   if x % y == 0:
       return y
   return gcd(y, x % y)

CD = (c * d) // gcd(c,d)

h_b =b - (b // c) - (b // d) + (b // CD)
h_a = (a - 1) - (a - 1) // c - (a - 1) // d + (a - 1) // CD

print(h_b - h_a)
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo_II(S,T,n):
  A=[0]*n
  counter=0
  for j1 in range(len(T)):
    if S[j1] ==T[j1]:counter+=1
    else: break
  A[0]=counter 
  i=1
  j=0
  while i<n:
    while i+j<len(S) and j<len(T):
      if S[i+j]==T[j]: j+=1
      else: break
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j=0
  B = [False]*n
  for i in range(n):
    if A[i]==len(T): B[i]=True
  return B

def dfs(pt,v):
  n=len(pt)
  d=[-1]*n
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return d

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = s*(len(t)//ls +2)
B = Z_algo_II(s2,t,ls)

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

ans = 0
for v in range(ls):
  tmp = max(dfs(pt,v))
  if tmp>ans:
    ans = tmp

print(ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  if visited[v]==True:
    return -1,visited
  S = [v]
  now = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if i != v:
        visited[i] = True
        now += 1
        S.append(i)
      else:
        print(-1)
        exit()
  return now,visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

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

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    r, c, cur_cost = dq.popleft()

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.appendleft((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    for x in range(-2, 3):
        r_new = r + x
        if r_new < 0 or r_new >= H:
            continue

        for y in range(-2, 3):
            c_new = c + y

            if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                continue

            dq.append((r_new, c_new, cur_cost + 1))
            search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

grid = [list(input()) for s in range(H)]
search = [[float('inf')] * W for _ in range(H)]

dq = deque([])
dq.append((Ch, Cw, 0))
search[Ch][Cw] = 0

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]

while dq:
    r, c, cur_cost = dq.popleft()

    for x, y in direction:
        r_new = r + x
        c_new = c + y

        if r_new < 0 or r_new >= H or c_new < 0 or c_new >= W or \
                search[r_new][c_new] <= cur_cost or grid[r_new][c_new] == '#':
            continue

        dq.appendleft((r_new, c_new, cur_cost))
        search[r_new][c_new] = cur_cost

    for x in range(-2, 3):
        r_new = r + x
        if r_new < 0 or r_new >= H:
            continue

        for y in range(-2, 3):
            c_new = c + y

            if c_new < 0 or c_new >= W or search[r_new][c_new] <= cur_cost + 1 or grid[r_new][c_new] == '#':
                continue

            dq.append((r_new, c_new, cur_cost + 1))
            search[r_new][c_new] = cur_cost + 1


if search[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(search[Dh][Dw])
### BUGGY CODE ###

#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    T = B[N - 1]

    i2 = bisect.bisect_left(B, T / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = T - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = T / 2 - min_d
    max_half = T / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2)

    for i2 in range(i2_lo, i2_hi + 1):
        if min_d * 2 < abs(T - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)
        i1_lo = i1_hi = i1
        i3_lo = i3_hi = i3
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != T + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi + 1):
            for i3 in range(i3_lo, i3_hi + 1):
                P = B[i1]
                Q = B[i2] - B[i1]
                R = B[i3] - B[i2]
                S = T - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    T = B[N - 1]

    i2 = bisect.bisect_left(B, T / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = T - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = T / 2 - min_d
    max_half = T / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2) + 1

    for i2 in range(i2_lo, i2_hi):
        if min_d * 2 < abs(T - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)
        i1_lo, i1_hi = i1, i1 + 1
        i3_lo, i3_hi = i3, i3 + 1
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != T + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi):
            P = B[i1]
            Q = B[i2] - B[i1]
            for i3 in range(i3_lo, i3_hi):
                R = B[i3] - B[i2]
                S = T - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


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

N, M = map(int, input().split())
cards = [True for x in range(N)]

for x in range(M):
    l, m = map(int, input().split())
    cards[0:l-1] = [False for y in range(0, l-1)]
    cards[m:] = [False for y in range(m, N)]
sum = 0
for x in cards:
    if x:
        sum = sum + 1

print(sum)

### FIXED CODE ###

N, M = map(int, input().split())
maxL = 0
minM = N
for x in range(M):
    l, m = map(int, input().split())
    maxL = max(maxL, l)
    minM = min(minM, m)

print(max(minM - maxL + 1, 0))
### BUGGY CODE ###

S=input()
Q=int(input())
r = False
for _ in range(Q):
  qs = input().split(' ')
  if len(qs) == 1:
    r = not r
  else:
    if (qs[1] == '1' and (not r)) or (qs[1] == '2' and r):
      S = qs[2] + S
    else:
      S = S + qs[2]
if r:
  print(S[::-1])
else:
  print(S)



### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
S=deque(input()[:-1])
Q=int(input())
r = False
for _ in range(Q):
  qs = input()[:-1].split(' ')
  if len(qs) == 1:
    r = not r
  else:
    if (qs[1] == '1' and (not r)) or (qs[1] == '2' and r):
      S.appendleft(qs[2])
    else:
      S.append(qs[2])
if r:
  print(''.join(reversed(S)))
else:
  print(''.join(S))
### BUGGY CODE ###

n=int(input())
v=list(map(int,input().split()))
v_odd=[]
v_even=[]
odd=[[0,0]]
even=[[0,0]]

for j in range(int(n/2)):
    v_odd.append(v[2*j])
    v_even.append(v[2*j+1])

for i in range(int(n/2)):
    odd.append([v_odd[i],v_odd.count(v_odd[i])])
    even.append([v_even[i],v_even.count(v_even[i])])

odd.sort(key=lambda x:(x[1],x[0]),reverse=True)
even.sort(key=lambda x:(x[1],x[0]),reverse=True)

if odd[0][0]!=even[0][0]:
    ans=n-odd[0][1]-even[0][1]
else:
    ans=min(n-odd[0][1]-even[even[0][1]][1],n-odd[odd[0][1]][1]-even[0][1])
    
print(ans)

### FIXED CODE ###

from collections import Counter, deque
n=int(input())
V=deque(list(map(int,input().split())))
if len(set(V))==1:print(n//2)
else:
    Odd=[]
    Even=[]
    for _ in range(n//2):
        Odd.append(V.popleft())
        Even.append(V.popleft())
    O=Counter(Odd)
    E=Counter(Even)
    if len(set(Odd))==1:print(n//2-E.most_common()[0][1])
    elif len(set(Even))==1:print(n//2-O.most_common()[0][1])
    elif O.most_common()[0][0]==E.most_common()[0][0]:print(min(n-E.most_common()[0][1]-O.most_common()[1][1],n-E.most_common()[1][1]-O.most_common()[0][1]))
    else:print(n-E.most_common()[0][1]-O.most_common()[0][1])
### BUGGY CODE ###

a,b,n=map(int,input().split())
score=0
if (n<b):
    print( int(a*n/b))
# elif(n<(a/b)):
#     print(0)
else:
    c = int(n/b)
    score = 0
    for i in range(1,c+1):
        n_ = b*i-1
        t = int(a*n_/b)-a*int(n_/b)
        score = max(score,t)
    t = int(a*n/b)-a*int(n/b)
    score = max(score,t)
    print(score)

### FIXED CODE ###

a,b,n=map(int,input().split())
score=0
if (n<b):
    print( int(a*n/b))
elif(b==1):
    print(0)
else:
    c = int(n/b)
    score = 0
    for i in range(1,c+1):
        n_ = b*i-1
        t = int(a*n_/b)-a*int(n_/b)
        score = max(score,t)
    t = int(a*n/b)-a*int(n/b)
    score = max(score,t)
    print(score)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
s = [input() for i in range(n)]
ans = {}
word_list = list(set(s))

for i in word_list:
  ans[i] = s.count(i)

for k, v in sorted(ans.items()):
  if v == max(ans.values()):
    print(k)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
ans = []
charctor_count = Counter(s)
max_count = max(charctor_count.values())
for k, v in charctor_count.items():
  if v == max_count:
    ans.append( k)
print("\n".join(sorted(ans)))
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
for _ in range(m):
    b, c = map(int, input().split())
    a_list.extend([c]*b)
a_list.sort(reverse=True)
print(sum(a_list[:n]))


### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
m_list = []
for _ in range(m):
    b, c = map(int, input().split())
    m_list.append([c, b])
m_list.sort(reverse=True)
cnt = 0
tmp_list = []
for c, b in m_list:
    if cnt < n:
        tmp_list += [c]*b
    else:
        break
    cnt += b
a_list.extend(tmp_list)
a_list.sort(reverse=True)
print(sum(a_list[:n]))
### BUGGY CODE ###

#Mo
n,q=map(int, input().split())
*c,=map(int, input().split())
que=[]
for i in range(q):
    li,ri=map(int, input().split())
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//700,x[1]))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for i in range(q):
    l,r,j=que[i]
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
print('\n'.join(map(str,ans[:q])))


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)
### BUGGY CODE ###

# -coding: utf-8 -

a,b,k = map(int, input().split())

s = [i for i in range(a,b+1)]
#print(s)

if len(s) < k*2:
    for i in s:
        print(i)

if len(s) >= k*2:
    s_left = s[:k]
    s_right = s[-k:]
    s2 = s_left+s_right
    for i in s2:
        print(i)

    


### FIXED CODE ###

# -coding: utf-8 -

a,b,k = map(int, input().split())

s = range(a,b+1)
s_small = s[:k]
s_large = s[-k:]
ans = list(set(s_small)|set(s_large))
ans = sorted(ans)
for i in ans:
    print(i)
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 0
for i in range(n - 2):
    for j in range(i + 1,n - 1):
        for k in range(j + 1,n):
            if s[i] == s[j] or s[j] == s[k] or s[i] == s[k]:
                continue
            elif j - i == k - j:
                continue
            else:
                ans += 1
               
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
ans = s.count("R")*s.count("G")*s.count("B")
for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:
            break
     
        if s[i] != s[j] and  s[i] != s[k] and s[k] != s[j]:
            ans -= 1
print(ans)
### BUGGY CODE ###

from itertools import combinations

def main(N, A):
    ans = 0
    for Ai, Aj in combinations(A, 2):
        ans += Ai*Aj
        ans = ans % (10**9 + 7)
    return ans

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    ans = main(N, A)
    print(ans)



### FIXED CODE ###

def main(N, A):
    ans = 0
    culm = sum(A)
    for i in range(N-1):
        culm -= A[i]
        ans += A[i]*culm
        ans %= 10**9 + 7
    return ans

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    ans = main(N, A)
    print(ans)