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

N = int(input())
v_list = [int(x) for x in input().split()]
s = list(set(v_list))
s.sort()
n = 0
count = []
for i in s:
        count.append(v_list.count(i))
if len(s) > 1:

        ind = v_list.index(s[-1])


        for i in range(ind - len(v_list) + 1, ind):
                if i % 2 == ind % 2:
                        if v_list[i] != s[-1]:
                                n += 1
                else:
                        if v_list[i] != s[-2]:
                                n += 1 

else:
        n = int(N / 2)



print(n)

### FIXED CODE ###

from collections import defaultdict
import sys
n = int(input())
v = list(map(int, input().split()))

dd_even = defaultdict(int)
dd_odd  = defaultdict(int)

# 偶数番目のヒストグラムを作る
for i in range(0, n, 2):
    dd_even[v[i]] += 1

l_even = list(dd_even.items())
l_even.sort(key= lambda x:x[1])
top_even = l_even[-1][0]
#print(l_even)

# 奇数番目のヒストグラムを作る
for i in range(1, n, 2):
    dd_odd[v[i]] += 1

l_odd = list(dd_odd.items())
l_odd.sort(key= lambda x:x[1])
#print(l_odd)
top_odd = l_odd[-1][0]

if top_even == top_odd:
    if len(l_odd) == 1: # つまり全部同じ数字のとき
        res = int(n / 2)
        print(res)
        sys.exit()
    else:
        # 2パターン試す
        l_odd_1 = [l for l in l_odd if l[0] != l_odd[-2][0]]
        sum_odd_1 = sum(l[1] for l in l_odd_1)
        l_even_1 = [l for l in l_even if l[0] != top_even]
        sum_even_1 = sum(l[1] for l in l_even_1)
        sum_1 = sum_odd_1 + sum_even_1

        l_odd_2 = [l for l in l_odd if l[0] != top_odd]
        sum_odd_2 = sum(l[1] for l in l_odd_2)
        l_even_2 = [l for l in l_even if l[0] != l_even[-2][0]]
        sum_even_2 = sum(l[1] for l in l_even_2)
        sum_2 = sum_odd_2 + sum_even_2

        if sum_1 < sum_2:
            print(sum_1)
        else:
            print(sum_2)
        sys.exit()
else:
    l_odd = [l for l in l_odd if l[0] != top_odd]

sum_odd = sum(l[1] for l in l_odd)
#print(l_odd, sum_odd)

l_even = [l for l in l_even if l[0] != top_even]
sum_even = sum(l[1] for l in l_even)
#print(l_even, sum_even)

res = sum_odd + sum_even
print(res)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
list = [1]
i = 0
num = a[0]
while True:
    if num in list:
        break
    list.append(num)
    num = a[num-1]

ind = list.index(num)

lroop = list[ind:]

if k <= ind+1:
    print(list[k])
    exit()
else:
    k = (k-(ind))%(len(lroop))
    print(lroop[k])

### FIXED CODE ###

import collections
n,k = map(int,input().split())
a = list(map(int,input().split()))
list = [1]
i = 0
num = a[0]
for i in range(3*n):
    list.append(num)
    num = a[num-1]

cnt = collections.Counter(list)
onevalue = [k for k,v in cnt.items() if v == 1]
lstart = len(onevalue)
lroop = len(set(list))-lstart

if k <= lstart:
    num = a[0]
    for i in range(k-1):
        num = a[num-1]
    print(num)
    exit()
elif lstart == 0:
    k = (k-lstart)%lroop
    num = 1
    for i in range(k):
        num = a[num-1]
    print(num)
    exit()
else:
    k = (k-lstart)%lroop
    num = a[0]
    if lstart > 0:
        for i in range(lstart-1):
            num = a[num-1]
    for i in range(k):
        num = a[num-1]
    print(num)
    exit()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from operator import itemgetter
import numpy as np

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

LRi = []
for i in range(M):
    L, R = map(int, input().split())
    LRi.append((L,R))

#
# LRi.sort(key=itemgetter(1))
#
pqi = []
for i in range(Q):
    p, q = map(int, input().split())
    pqi.append((p,q))

Xi = np.zeros((N+1,N+1),dtype=np.int32)
for (L,R) in LRi:
    Xi[L][R] += 1

# print(Xi)

Ci = np.zeros((N+1,N+1),dtype=np.int32)
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# print(Ci)

for (p, q) in pqi:
    tmp = 0
    for l in range(p,q+1):
        tmp += Ci[l][q] - Ci[l][p-1]

    print(tmp)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# import numpy as np

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

# Xi = np.zeros((N+1,N+1),dtype=np.int32)
Xi = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    Xi[L][R] += 1

# Ci = np.zeros((N+1,N+1),dtype=np.int32)
Ci = [[0]*(N+1) for i in range(N+1)]
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# print(Ci)

for r in range(N+1):
    tmp = 0
    for l in range(N+1):
        tmp += Ci[l][r]
        Ci[l][r] = tmp

# print(Ci)

pqi = []
for i in range(Q):
    p, q = map(int, input().split())
    pqi.append((p,q))

for (p, q) in pqi:
    tmp = Ci[q][q] - Ci[q][p-1]  - Ci[p-1][q] + Ci[p-1][p-1]
    print(tmp)
### BUGGY CODE ###

from collections import deque, defaultdict
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[2])
ans = [0 for i in range(q)]
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0 
num = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball : 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    pre_r = r
    ans[index] = query(l,r+1)
for i in range(q):
    print(ans[i])

### FIXED CODE ###

from sys import stdin
input = stdin.readline
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[2])
ans = [0 for i in range(q)]
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0 
num = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
count = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball: 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    pre_r = r + 1
    ans[index] = query(l, r+1)
for i in range(q):
    print(ans[i])
### BUGGY CODE ###

import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n,x,y=map(int,input().split())


l1=n-y-x
l2=y-x

l=[0]*(n-1)
k=0
a=0
b=0
c=0
for i in range(1,n):
	for j in range(i+1,n+1):
		a=j-i
		b=abs(i-x)+1+abs(j-y)
		c=abs(i-y)+1+abs(j-x)
		k=min(a,b,c)
		l[k-1]+=1
		k=0
		a=0
		b=0
		c=0

for j in range(n-1):
	print(l[j])	

		
	

### FIXED CODE ###

import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n,x,y=map(int,input().split())


l1=n-y-x
l2=y-x

l=[0]*(n-1)
k=0
for i in range(1,n):
	for j in range(i+1,n+1):
		k=min(j-i,abs(i-x)+1+abs(j-y),abs(i-y)+1+abs(j-x))
		l[k-1]+=1
		k=0

for j in range(n-1):
	print(l[j])
### BUGGY CODE ###

#!/usr/bin/env python3

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    ta = [list(map(int, input().split())) for _ in range(n)]
    ans = sum(ta[0])
    for i in range(1, n):
        si1 = sum(ta[i - 1])
        si = sum(ta[i])
        tmp = si
        while tmp * ta[i][0] // si < ans * ta[i - 1][0] // si1 or tmp * ta[i][1] // si < ans * ta[i - 1][1] // si1:
            tmp += si
        ans = tmp
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

#!/usr/bin/env python3

from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    ta = [list(map(int, input().split())) for _ in range(n)]
    ans = sum(ta[0])
    for i in range(1, n):
        si1 = sum(ta[i - 1])
        si = sum(ta[i])
        cand1 = (ans * ta[i - 1][0] // si1) // ta[i][0] if (ans * ta[i - 1][0] // si1) % ta[i][0] == 0 else (ans * ta[i - 1][0] // si1) // ta[i][0] + 1
        cand2 = (ans * ta[i - 1][1] // si1) // ta[i][1] if (ans * ta[i - 1][1] // si1) % ta[i][1] == 0 else (ans * ta[i - 1][1] // si1) // ta[i][1] + 1
        ans = si * max([cand1, cand2])
    print(ans)


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

import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

INF = 10**5
n, m = map(int, input().split())
e = [INF for _ in range(n)]
e[n-1] = 0
adj = [[] for _ in range(n)]
farthest = [0 for _ in range(n)]
for _ in range(m):
	s, t = map(int, input().split())
	adj[s-1].append(t-1)

for x in range(n-2, -1, -1):
	if adj[x] == [n-1]:
		e[x] = 1		
	else:		
		su = 0
		for v in adj[x]:
			su += e[v]
			farthest[x] = max(farthest[x], e[v])
		e[x] = su/len(adj[x]) + 1

ans = e[0]

for i in range(n-1):
	f = e
	if len(adj[i]) == 1:
		f[i] = INF
	else:
		f[i] = ((e[i] - 1) * len(adj[i]) - farthest[i]) / (len(adj[i]) - 1) + 1

	for x in range(i-1, -1, -1):
		if adj[x] == [n-1]:
			f[x] = 1		
		else:		
			su = 0
			for v in adj[x]:
				if f[v] == INF:
					f[x] = INF
					break
				su += f[v]
			else:
				f[x] = su/len(adj[x]) + 1
	ans = min(ans, f[0])

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]

INF = 10**5
n, m = map(int, input().split())
e = [INF for _ in range(n)]
e[n-1] = 0
adj = [[] for _ in range(n)]
farthest = [0 for _ in range(n)]
for _ in range(m):
	s, t = map(int, input().split())
	adj[s-1].append(t-1)

for x in range(n-2, -1, -1):
	if adj[x] == [n-1]:
		e[x] = 1		
	else:		
		su = 0
		for v in adj[x]:
			su += e[v]
			farthest[x] = max(farthest[x], e[v])
		e[x] = su/len(adj[x]) + 1

ans = e[0]

for i in range(n-1):
	f = e
	if len(adj[i]) == 1:
		f[i] = INF
	else:
		f[i] = ((e[i] - 1) * len(adj[i]) - farthest[i]) / (len(adj[i]) - 1) + 1

	for x in range(i-1, -1, -1):
		if adj[x] == [n-1]:
			f[x] = 1		
		else:		
			su = 0
			for v in adj[x]:
				if f[v] == INF:
					f[x] = INF
					break
				su += f[v]
			else:
				f[x] = su/len(adj[x]) + 1
	ans = min(ans, f[0])

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

N,K=list(map(int,input().split()))
dp_list=[10**10]*110000
h=list(map(int,input().split()))
for _ in range(K):h.append(0)
dp_list[0]=0
for i in range(N):
    for j in range(1,K+1):
        k=i+j
        dp_list[k]=min(dp_list[k],abs(h[k]-h[i])+dp_list[i])
print(dp_list[N-1])

### FIXED CODE ###

import numpy as np
N,K=list(map(int,input().split()))
dp_list=np.full(N,10**10,dtype=int)
h=list(map(int,input().split()))
h=np.array(h)
dp_list[0]=0
for i in range(1,N):
        dp_list[i:i+K] = np.fmin(dp_list[i:i+K], dp_list[i-1] + np.abs(h[i:i+K] - h[i-1]))
print(dp_list[-1])
### BUGGY CODE ###

n = int(input())

arr = []
max_num = 0
label = 1
for i in range(n):
    inp = int(input())
    if inp >= max_num:
       max_num = inp
       label = i
    arr.append(inp)


arr_sub = arr[:]
arr_sub.pop(label)
#print(arr)
#print(max(arr))
#print(max(arr_sub))



for i in range(n):
    if i != label:
        print(max(arr))
    else:
        print(max(arr_sub))




### FIXED CODE ###

n = int(input())

arr = []
max_num = 0
label = 1
for i in range(n):
    inp = int(input())
    if inp >= max_num:
       max_num = inp
       label = i
    arr.append(inp)



arr_sub = arr[:]
arr_sub.pop(label)
second_max = max(arr_sub)


for i in range(n):
    if i != label:
        print(max_num)
    else:
        print(second_max)
### BUGGY CODE ###

n, k = map(int, input().split())
p_i = list(map(int,input().split()))
answer = 0
for x in range(n - k + 1):
    answer = max(answer, sum(p_i[x : x + k]))
print((answer + k) / 2)

### FIXED CODE ###

n, k = map(int, input().split())
p_i = list(map(int,input().split()))
answer = 0
sum = 0
for x in range(n):
    if x <= k - 1: 
        sum += p_i[x]
        if x == k - 1: answer = sum
    else:
        sum += p_i[x] - p_i[x - k]
        answer = max(answer, sum)
print((answer + k) / 2)
### BUGGY CODE ###

import math


def kumiawase(n):
    if n == 0 or n == 1:
        return 0
    return math.floor(math.factorial(n) / math.factorial(n - 2) / 2)


n = int(input())
aL = list(map(int, input().split(" ")))

d = {}

for a in aL:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

d2 = {}
d3 = {}

for dk, di in d.items():
    d2[dk] = kumiawase(di)
    d3[dk] = kumiawase(di - 1)

for a in aL:
    sm = sum(d2.values())
    print(sm - d2[a] + d3[a])


### FIXED CODE ###

import math
import collections


def kumiawase(n):
    if n == 0 or n == 1:
        return 0
    return (n**2 - n) // 2


n = int(input())
aL = list(map(int, input().split(" ")))

d = collections.Counter(aL)

s = 0
for i in d.values():
    s += kumiawase(i)

for a in aL:
    print(s - d[a] + 1)
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
pre = []
year = []
year_order = [0 for i in range(m)]
each_arr = [[] for i in range(n)]
each_sort = [[] for i in range(n)]
each_order = [[] for i in range(n)]

for i in range(m):
    p, y = [int(i) for i in input().split()]
    pre.append(p)
    year.append(y)


for i in range(m):
    each_arr[pre[i]-1].append(year[i])

for j in range(n):
    each_sort[j] = sorted(each_arr[j])
    each_order[j] = [each_sort[j].index(i)+1 for i in each_arr[j]]

for i in range(m):
    year_order[i] = each_order[pre[i]-1][0]
    each_order[pre[i]-1].remove(each_order[pre[i]-1][0])

pre = [format(str(i), '0>6') for i in pre]
year_order = [format(str(i), '0>6') for i in year_order]

for i in range(m):
    print(pre[i]+year_order[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
L = []
for i in range(M):
    P, Y = map(int, input().split())
    L.append([P, Y, i])

L = sorted(L)

reset = 0
count = 0
ans = []
for i in range(M):
    if L[i][0] != reset:
        reset = L[i][0]
        count = 1
    else:
        count += 1
    
    ans.append([L[i][2], str(reset).zfill(6) + str(count).zfill(6)])

ans = sorted(ans)

for i in range(M):
    print(ans[i][1])
### BUGGY CODE ###

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

sum_ = 0
for i in range(N):
  for j in range(N):
    if (i<=j):
      continue
    if As[i] == As[j]:
      sum_ += 1

dic = {}
for i in list(set(As)):
  dic[i] = As.count(i)-1
      
for i in range(N):
  print(sum_-dic[As[i]])

### FIXED CODE ###

import collections
N = int(input())
As = list(map(int, input().split()))

c = collections.Counter(As)

sum_ = 0
for key, val in c.items():
  sum_ += (val*(val-1)/2)

sum_ = int(sum_)

for i in range(N):
  print(sum_-(c[As[i]]-1))
### BUGGY CODE ###

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

    total = 0
    for idx, i in enumerate(A):
        if idx + 1 == len(A):
            break
        total += i * sum(A[idx + 1:])
    print(total % (10**9 + 7))


def main():
    probC()


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    sum_tail = sum(A)

    total = 0
    for idx, i in enumerate(A):
        sum_tail -= A[idx]
        if idx + 1 == len(A):
            break
        total += i * sum_tail
    print(total % (10**9 + 7))


def main():
    probC()


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

N = int(input())

start = 0
end = N

print(0)
s0 = input()
if s0 == 'Vacant':
    exit()

ni = (start+end)//2
print(ni, flush=True)
s = input()

while s != 'Vacant':
    if not((s == s0) ^ ((s % 2) == (s0 % 2))):
        end = ni
    else:
        start = ni

    s0 = s

    ni = (start+end)//2
    print(ni, flush=True)
    s = input()


### FIXED CODE ###

N = int(input())


def ask(i):
    print(i, flush=True)
    resp = input()
    if resp == 'Vacant':
        exit()
    return resp


def test(l, r, l_resp, r_resp):
    if l % 2 == r % 2:
        return l_resp == r_resp
    else:
        return l_resp != r_resp


resp = ask(0)

l = 0
r = N
l_resp = resp
r_resp = resp

for _ in range(19):
    m = (l+r)//2
    m_resp = ask(m)
    if test(l, m, l_resp, m_resp):
        l, l_resp = m, m_resp
    else:
        r, r_resp = m, m_resp
### BUGGY CODE ###

import bisect
N,Q = (int(x) for x in input().split())

stop_arr = [(0,0,0) for _ in range(N)]
for i in range(N):
    S,T,X = (int(x) for x in input().split())
    stop_arr[i] = (S,T,X)
Q_arr = [0 for _ in range(Q)]
for i in range(Q):
    Q_arr[i] = int(input())

stop_arr_ind = list(range(N))
stop_arr_ind.sort(key=lambda x:stop_arr[x][2], reverse=True)
# stop_arr.sort(key=lambda x:x[2], reverse=True)
ans_arr = [-1]*Q

for i in stop_arr_ind:
    s,t,x = stop_arr[i]
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    for i in range(q_start, q_stop):
        ans_arr[i] = x

for a in ans_arr:
    print(a)


### FIXED CODE ###

import bisect

N,Q = (int(x) for x in input().split())

stop_arr = [tuple(map(int, input().split())) for _ in range(N)]
Q_arr = [int(input()) for _ in range(Q)]

stop_arr_ind = list(range(N))
stop_arr_ind.sort(key=lambda x:stop_arr[x][2])
# stop_arr.sort(key=lambda x:x[2], reverse=True)
ans_arr = [-1]*Q
skip_arr = [-1]*(Q+1)

def update_skip(skip_arr, x):
    if skip_arr[x] == -1:
        return x
    x_dest = update_skip(skip_arr, skip_arr[x])
    skip_arr[x] = x_dest
    return x_dest

for i in stop_arr_ind:
    s,t,x = stop_arr[i]
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    l = q_start
    while l < q_stop:
        if skip_arr[l] == -1:
            skip_arr[l] = q_stop
            ans_arr[l] = x
            l += 1
        else:
            l = update_skip(skip_arr, l)

print(*ans_arr, sep="\n")
### BUGGY CODE ###

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

import math

Asum = sum(A)
candidates = []
for i in range(1, int(math.sqrt(Asum)) + 1):
    if Asum % i == 0:
        candidates.append(i)
        candidates.append(Asum // i)
candidates.sort()

# print("#", Asum)
# print("#", candidates)

ans = 1
for targ in candidates:
    if targ == 1: continue
    A_tmp = [(Ai % targ) for Ai in A]
    # A_tmp.sort(key=lambda x: min((x % targ), ((targ - x) % x)))
    A_tmp.sort()
    idx_l = 0
    idx_r = N - 1
    cnt = 0
    while sum(A_tmp) > 0:
        cap_l = A_tmp[idx_l]
        cap_r = targ - A_tmp[idx_r]
        A_tmp[idx_l] = (A_tmp[idx_l] - min(cap_l, cap_r)) % targ
        A_tmp[idx_r] = (A_tmp[idx_r] + min(cap_l, cap_r)) % targ
        cnt += min(cap_l, cap_r)
        if A_tmp[idx_l] == 0:
            idx_l += 1
        if A_tmp[idx_r] == 0:
            idx_r -= 1
    #
    if cnt <= K: ans = targ

print(ans)

### FIXED CODE ###

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

import math

Asum = sum(A)
candidates = []
for i in range(1, int(math.sqrt(Asum)) + 1):
    if Asum % i == 0:
        candidates.append(i)
        candidates.append(Asum // i)
candidates.sort()

# print("#", Asum)
# print("#", candidates)

ans = 1
for targ in candidates:
    if targ == 1: continue
    A_tmp = [(Ai % targ) for Ai in A]
    # A_tmp.sort(key=lambda x: min((x % targ), ((targ - x) % x)))
    A_tmp.sort()
    idx_l = 0
    idx_r = N - 1
    cnt = 0
    while sum(A_tmp) > 0 and idx_l < idx_r:
        cap_l = A_tmp[idx_l]
        cap_r = targ - A_tmp[idx_r]
        A_tmp[idx_l] = (A_tmp[idx_l] - min(cap_l, cap_r)) % targ
        A_tmp[idx_r] = (A_tmp[idx_r] + min(cap_l, cap_r)) % targ
        cnt += min(cap_l, cap_r)
        if A_tmp[idx_l] == 0:
            idx_l += 1
        if A_tmp[idx_r] == 0:
            idx_r -= 1
    #
    if cnt <= K and sum(A_tmp) == 0: ans = targ

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

def make_ps(n):
    tbl = [False, True, False, False, False, True] * (n // 6 + 1)
    for i in range(1, 4):
        tbl[i] = not tbl[i]
    p, stp, sqrt = 5, 2, n ** 0.5
    while p < sqrt:
        for i in range(p ** 2, n, 2 * p):
            tbl[i] = False
        while True:
            p += stp
            stp = 6 - stp
            if tbl[p]:
                break
    return [i for i in range(n) if tbl[i]]
ps = make_ps(50000)
while True:
    n = int(input())
    if not n:
        break
    if n % 2:
        print(1 if n - 2 in ps else 0)
    else:
        res = 0
        for p in ps:
            if p > n / 2:
                break
            if n - p in ps:
                res += 1
        print(res)

### FIXED CODE ###

def make_tbl(n):
    tbl = [False, True, False, False, False, True] * (n // 6 + 1)
    for i in range(1, 4):
        tbl[i] = not tbl[i]
    p, stp, sqrt = 5, 2, n ** 0.5
    while p < sqrt:
        for i in range(p ** 2, n, 2 * p):
            tbl[i] = False
        while True:
            p += stp
            stp = 6 - stp
            if tbl[p]:
                break
    return tbl
tbl = make_tbl(50000)
ps = [i for i in range(50000) if tbl[i]]
while True:
    n = int(input())
    if not n:
        break
    res = 0
    if n % 2:
        if tbl[n - 2]:
            res += 1
    else:
        res = 0
        for p in ps:
            if 2 * p > n:
                break
            if tbl[n - p]:
                res += 1
    print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

match=[None,2,5,5,4,5,6,3,7,6]


dp=[ None for i in range(N+1) ] 
dp[0]=""


for i in range(N):
	if dp[i] is not None:
		for a in A:
			match_cnt=match[a]
			if 0<=i+match_cnt<=N:
				if dp[i+match_cnt] is None:
					dp[i+match_cnt]=dp[i]+str(a)
				else:
					if int(dp[i+match_cnt]) < int( dp[i]+str(a) ):
						dp[i+match_cnt]=dp[i]+str(a)				

print dp[N]

### FIXED CODE ###

T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]

N,M=map(int, raw_input().split())
A=map(int, raw_input().split())


P=[]
for i in A:
	P.append(T[i-1])


dp=[ None for i in range(N+1) ]
dp[0]=""


for i in range(N):
	#print "i :::: ",i,dp
	if dp[i] is not None:
		for num, match in P:
			if i+match<=N:

				if dp[i+match] is None:
					dp[i+match]=dp[i]+str(num)
				else:
					l1=len(dp[i+match])
					l2=len(dp[i]+str(num))
					if l1>l2:
						pass
					elif l1<l2:
						dp[i+match]=dp[i]+str(num)
					else:
						dp[i+match]=max( dp[i+match] , dp[i]+str(num) )


print dp[N]
### BUGGY CODE ###

N, A, B = map(int, input().split())
ball = []
kaisu = -(-N//(A+B))

for n in range(kaisu):
    for i in range(A):
        ball.append(0)
    for j in range(B):
        ball.append(1)

ball = ball[:N]

print(ball.count(0))

### FIXED CODE ###

N, A, B = map(int, input().split())
kaisu = N//(A+B)

n = N-((A+B)*kaisu)
if n >= A:
    print(A*(kaisu+1))
else:
    print(A*kaisu+n)