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

N, M = map(int, input().split())
L = []
R = []
ans = 0
tmp = 1
for _ in range(M):
    inp = input().split()
    L.append(int(inp[0]))
    R.append(int(inp[1]))
for k in range(1,N + 1):
    for i,j in zip(L,R):
        if tmp == 1:
            if i <= k and k <= j:
                tmp *= 1
            else:
                tmp *= 0
        else:
            break
    if tmp == 1:
        ans += 1
    else:
        tmp = 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
L = []
R = []
ans = 0
for _ in range(M):
    inp = input().split()
    L.append(int(inp[0]))
    R.append(int(inp[1]))
L_max = max(L)
R_min = min(R)
for i in range(L_max,min(R_min,N) + 1):
    ans  += 1
print(ans)
### BUGGY CODE ###

s = int(input())
k = int(input())
 
ans=0
 
n  = 5000000000000000
 
S = str(s) #文字列にする
saisho = 0
 
for i in range(len(S)):
  N = int(S[i])
  if k <= saisho+1:#最初からの文字数
    ans = N
    break
    
  else:
    if N ==1:
      Nn = 1
    else:
      Nn = N**n
    saisho += Nn
    
print(ans)

### FIXED CODE ###

s = int(input())
k = int(input())
S = str(s) #文字列にする

ans=0

for i in range(k):
  N = int(S[i])
  
  if N == 1:
    ans = 1
  else:
    ans = N
    break  
print(ans)
### BUGGY CODE ###

import copy

s = input()
t = input()

a = [[] for i in range(26)]
for i in range(len(s)):
    num = ord(s[i]) - 97
    a[num].append(i)

flg = True
cnt = 0
x = -1
for i in range(len(t)):
    num = ord(t[i]) - 97
    if not a[num]:
        flg = False
        break
    for j in range(len(a[num])):
        if x < a[num][j]:
            x = copy.deepcopy(a[num][j])
            break
        if j == len(a[num])-1:
            cnt += 1
            x = copy.deepcopy(a[num][0])
            break
print(cnt*len(s) + x+1) if flg else print(-1)

### FIXED CODE ###

import copy

s = input()
t = input()

sn = len(s)
tn = len(t)
a = [[] for i in range(26)]
for i in range(sn):
    num = ord(s[i]) - 97
    a[num].append(i)

table = [[0]*sn for i in range(26)]
for i in range(26):
    if a[i]:
        table[i][:] = [copy.deepcopy(a[i][0])]*sn
    f = 0
    for j in a[i]:
        table[i][f:j] = [copy.deepcopy(j)]*(j-f)
        f = copy.deepcopy(j)

flg = True
cnt = 0 # 今何週したか
x = -1 # 今何文字目か
for i in range(tn):
    num = ord(t[i]) - 97
    # sの中に対象の文字が存在しない
    if not a[num]:
        flg = False
        break
    # sの中に対象の文字が存在
    xx = copy.deepcopy(x)
    x = table[num][x]
    if xx >= x:
        cnt += 1
print(cnt*sn + x+1) if flg else print(-1)
### BUGGY CODE ###

n, m, q = map(int, input().split())
start_sets = [set() for _ in range(n+2)]
end_sets = [set() for _ in range(n+2)]
for i in range(m):
    l, r = map(int, input().split())
    start_sets[l].add(i)
    end_sets[r].add(i)

for i in range(1, n+2):
    start_sets[i] |= start_sets[i-1]
    end_sets[i] |= end_sets[i-1]

ans = []
for _ in range(q):
    p, q = map(int, input().split())
    start = start_sets[q]-start_sets[p-1]
    end = end_sets[q] - end_sets[p-1]
    res = start & end
    ans.append(len(res))
print(*ans, sep="\n")

### FIXED CODE ###

N,M,Q = map(int,input().split())
l = [[0 for i in range(N)] for j in range(N)]
 
for _ in range(M):
    L,R = map(int,input().split())
    l[L-1][R-1] += 1
 
csum = [[0 for i in range(N+1)] for j in range(N+1)]
 
for i in range(1,N+1):
    for j in range(1,N+1):
        csum[i][j] = csum[i][j-1] + csum[i-1][j] - csum[i-1][j-1] + l[i-1][j-1]
 
for _ in range(Q):
    p,q = map(int,input().split())
    print(csum[q][q]-csum[q][p-1]-csum[p-1][q]+csum[p-1][p-1])
### BUGGY CODE ###

import math
n = int(input())
res = 1
tab = [int(n) for n in input().split()]
for i in tab:
    res = res * i
if res > pow(10, 18):
  print("-1")
else:
  print(res)

### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
	if 0 in A:
		print(0)
		return
	prod = 1
	for a in A:
		prod *= a
		if prod > 1000000000000000000:
			print(-1)
			return
	print(prod)
main()
### BUGGY CODE ###

n = int(input())

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

i = 0
x = 1
while i < n:
    x = x * a[i]
    i += 1

if x > 1000000000000000000:
    print(-1)
else:
    print(x)

### FIXED CODE ###

n = int(input())

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

i = 0
x = 1
while i < n:
    x = x * a[i]
    i += 1
    if x > 1000000000000000000:
        print(-1)
        exit()

print(x)
### BUGGY CODE ###

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

count = 1
for i in range(1, N):
    if P[i] == min(P[:i+1]):
        count += 1
print(count)

### FIXED CODE ###

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

mini = 10 ** 9
count = 0
for i in range(N):
    if P[i] <= mini:
        mini = P[i]
        count += 1
print(count)
### BUGGY CODE ###

k,q=map(int,input().split())
D=list(map(int,input().split()))
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    ans+=mD.count(0)*((n-1)//k)+mD[:((n-1)%k)].count(0) #0の数
    cnt=x%m+sum(mD)*((n-1)//k)+sum(mD[:((n-1)%k)]) #増えた量
    ans+=cnt//m
    print(n-1-ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=list(map(int,input().split()))
A=[]
for i in range(q):
    n,x,m=map(int,input().split())
    mD=list(map(lambda i: i%m, D)) #元の列のmodを取る
    ans=0
    cnt=x%m
    a=(n-1)//k
    b=(n-1)%k
    for d in mD[:b]: #mod kで余る部分
        if d==0:
            ans+=a+1
        cnt+=d*(a+1)
    for d in mD[b:]: #余らない部分
        if d==0:
            ans+=a
        cnt+=d*a
    ans+=cnt//m
    print(n-1-ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G = [[] for _ in range(N + 1)]
for el in XYZ:
    x, y, z = el
    G[x].append(y)
    G[y].append(x)

seen=[False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)

cnt = 0
for start in range(1, N + 1):
    if seen[start] == False:
        dfs(start)
        cnt += 1
print(cnt)


### FIXED CODE ###

import queue
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

seen=[False]*(N+1)
todo=queue.Queue()
def bfs(n):
    seen[n]=True
    for nxt in G[n]:
        if seen[nxt]==False:
            bfs(nxt)


cnt=0
for check in range(1, N+1):
    if seen[check]==False:
        cnt+=1
        bfs(check)
print(cnt)
### BUGGY CODE ###

import sys
h,w=map(int,input().split())
cmap=[input() for _ in range(h)]

whitesum=0
for each in cmap:
    whitesum += each.count(".")

def nextpoint(y,x):
    global cmap
    tmp=[]
    returnlist=[]
    cmap[y]=cmap[y][:x] + "#" + cmap[y][x+1:]

    if y == 0:
        tmp.append([y+1,x])
    elif y == h-1:
        tmp.append([y-1,x])
    else:
        tmp.extend([[y-1,x],[y+1,x]])

    if x == 0:
        tmp.append([y,x+1])
    elif x == w-1:
        tmp.append([y,x-1])
    else:
        tmp.extend([[y,x+1],[y,x-1]])

    for l in tmp:
        if cmap[l[0]][l[1]] == ".":
            returnlist.append(l)

    return returnlist

start=[0,0]
seen=[start]
todo=[]
todo.extend(nextpoint(start[0],start[1]))

i=2

while todo != []:
    nextlist=[]

    for nep in todo:
        if nep == [h-1,w-1]:
            print(whitesum-i)
            sys.exit()
        else:
            nextlist.extend(nextpoint(nep[0],nep[1]))
    todo=[]
    for rep in nextlist:
        todo.append(rep)

    i += 1

print("-1")



### FIXED CODE ###

import sys
h,w=map(int,input().split())
cmap=[input() for _ in range(h)]

whitesum=0
for each in cmap:
    whitesum += each.count(".")

def nextpoint(y,x):
    global cmap
    tmp=[]
    returnlist=[]
    cmap[y]=cmap[y][:x] + "#" + cmap[y][x+1:]

    if y == 0:
        tmp.append([y+1,x])
    elif y == h-1:
        tmp.append([y-1,x])
    else:
        tmp.extend([[y-1,x],[y+1,x]])

    if x == 0:
        tmp.append([y,x+1])
    elif x == w-1:
        tmp.append([y,x-1])
    else:
        tmp.extend([[y,x+1],[y,x-1]])

    for l in tmp:
        if cmap[l[0]][l[1]] == ".":
            cmap[l[0]]=cmap[l[0]][:l[1]] + "#" + cmap[l[0]][l[1]+1:]
            returnlist.append(l)

    return returnlist

start=[0,0]
seen=[start]
todo=[]
todo.extend(nextpoint(start[0],start[1]))

i=2
finishflag=True

while finishflag:
    nextlist=[]

    for nep in todo:
        if nep == [h-1,w-1]:
            print(whitesum-i)
            sys.exit()
        else:
            nextlist.extend(nextpoint(nep[0],nep[1]))
    todo=[]
    todo.extend(nextlist)

    if todo == []:
        finishflag = False

    i += 1

print("-1")
### BUGGY CODE ###

s = list(str(input()))
ans = 0
drop = False
for r in range(1, len(s)):
    if drop == False:
        l = r - 1
        if s[l] != -1 and s[l] != s[r]:
            ans += 2
            s[l], s[r] = -1, -1
            drop = True
    elif drop == True:
        while l >= 0 and s[l] == -1:
            l -= 1
        if l == -1 or s[l] == s[r]:
            drop = False
            continue
        if s[l] != s[r]:
            ans += 2
            s[l], s[r] = -1, -1
print(ans)

### FIXED CODE ###

s = str(input())
c0 = s.count('0')
c1 = s.count('1')
print(2 * min(c0, c1))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n, k = MAP()
    p = LIST()

    ans = []

    dic = defaultdict(int)

    for i in range(n-k+1):
        q = p[i:i+k]
        dic[i] = sum(q)

    #print(dic)
    ma = max(dic.values())
    dic_ = sorted(dic.items(), key=lambda x:x[1], reverse = True)
    #print(dic_)

    for i, x in dic_:
        if x != ma:
            break

        tmp = 0
        #print('-----', p[i:i+k])
        for x in p[i:i+k]:
            tmp += sum(range(1, x+1))/x
        
        ans.append(tmp)

    print(max(ans))

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n, k = MAP()
    p = LIST()
    ans = 0
    tmp = 0
    if n == k:
        k = list(accumulate(range(max(p)+1)))
        for x in p:
            ans += k[x]/x
        
        print(ans)
        sys.exit()

    p_ = list(accumulate(p))
    #print(p_)


    for i in range(n-k):
        #print(i,p_[i+k]-p_[i])
        if tmp <= p_[i+k]-p_[i]:
            l = p[i+1:i+k+1]
            tmp = p_[i+k]-p_[i]

    #print('l:',l)
    k = list(accumulate(range(max(l)+1)))

    for x in l:
        ans += k[x]/x
        
    print(ans)

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

S = list(map(int,input().split()))
N=S[0]
M=S[1]
count = 0
for i in range(N):
    if N ==0 or M<=1:
        break
    N=N-1
    M=M-2
    count += 1
if N==0:
    for i in range(M):
        if M>=4:
            M -= 4
            count += 1
print(count)

### FIXED CODE ###

S = list(map(int,input().split()))
N=S[0]
M=S[1]
N1=0
M1=0
count = 0

if 2*N<=M:
    count = N
    N1=0
    M1=M-2*N
    count+=M1//4
elif M<2*N:
    count += M//2
print(count)
### BUGGY CODE ###

from collections import deque

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

A = [list(input()) for _ in range(H)]

queue = deque([])

cnt = 0
black = 0

while True:
    f = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                queue.append((i, j))
                black += 1
            elif A[i][j] == ".":
                f = 1

    if not f:
        break
    while queue:
        h, w = queue.popleft()
        for i in [h-1, h+1]:
                if i >= 0 and i < H:
                    if A[i][w] == ".":
                        A[i][w] = "#"
                        # queue.append((i, w))
        for j in [w-1, w+1]:
            if j >= 0 and j < W:
                if A[h][j] == ".":
                    A[h][j] = "#"
                    # queue.append((h, j))
    cnt += 1
    # print(A)

print(cnt)


### FIXED CODE ###

from collections import deque

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

grid = [[-1]*W for _ in range(H)]

queue = deque([])

ans = 0

# while True:
#     f = 0
for i in range(H):
    s = input()
    for j, ss in enumerate(s):
        if ss =="#":
            queue.append((i, j))
            grid[i][j] = 0

#黒点をスタート地点とし、上下左右に移動した時の移動距離を記録していく
while queue:
    h, w = queue.popleft()
    for i in [h-1, h+1]:
            if i >= 0 and i < H:
                if grid[i][w] == -1:
                    grid[i][w] = grid[h][w]+1
                    queue.append((i, w))
    for j in [w-1, w+1]:
        if j >= 0 and j < W:
            if grid[h][j] == -1:
                grid[h][j] = grid[h][w]+1
                queue.append((h, j))

# print(grid)
print(max([max(b) for b in grid]))
### BUGGY CODE ###

#!/usr/bin/env python3
N, C = map(int, input().split())
table = [[0] * C for i in range(2 * 10 ** 5 + 2)]
for i in range(N):
    s, t, c = map(int, input().split())
    table[2 * s - 1][c - 1] = 1
    table[2 * t][c - 1] = -1

ans = [0] * (2 * 10 ** 5 + 2)
for i in range(1, 2 * 10 ** 5 + 2):
    for j in range(C):
        if table[i - 1][j] == 1 and table[i][j] == 0:
            table[i][j] = 1
    ans[i] = sum(map(lambda x: abs(x), table[i]))

print(max(ans[1:]))


### FIXED CODE ###

#!/usr/bin/env python3
N, C = map(int, input().split())
table = [[0] * C for i in range(10 ** 5 + 1)]
for i in range(N):
    s, t, c = map(int, input().split())
    table[s - 1][c - 1] += 1
    table[t - 1][c - 1] -= 1

imos = [0] * (10 ** 5 + 1)
for i in range(10 ** 5 + 1):
    for j in range(C):
        if table[i][j] == 1:
            imos[i] += 1
        if table[i][j] == -1:
            imos[i + 1] -= 1

ans = 0
for i in range(1, 10 ** 5 + 1):
    imos[i] += imos[i - 1]
    ans = max(ans, imos[i])

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

N,M=map(int,input().split())
S=set()
for i in range(N):
  S.add(i+1)
for i in range(M):
  L,R=map(int,input().split())
  T=set()
  for i in range(L,R+1):
    T.add(i)
  S=S&T
print(len(S))


### FIXED CODE ###

N,M=map(int,input().split())
L=1
R=100000
for i in range(M):
  l,r=map(int,input().split())
  L=max(L,l)
  R=min(r,R)
if L>R :
  print(0)
else :
  print(R-L+1)
### 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()))

ansList=[]
for m in range(x):
  for n in range(y):
    for o in range(z):
      ansList.append(a[m]+b[n]+c[o])

ansList.sort()
ansList.reverse()

for i in range(k):
  print(ansList[i])


### FIXED 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)

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]

for i in c:
  for j in ansListab:
    ansList.append(i+j)

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])
### BUGGY CODE ###

# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
n, k = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
ans = [0 for _ in range(n)]

for i in range(1, n):
	t = int(1e9)

	for j in range(1, k+1):
		if i-j >= 0: t = min(t, ans[i-j] + abs(q[i-j] - q[i]))

	ans[i] = t

print(ans[n-1])


### FIXED CODE ###

# ===================================
# (c) MidAndFeed aka ASilentVoice
# ===================================
# import math 
# import collections
# import string
# ===================================
import numpy as np
n, k = [int(x) for x in input().split()]
q = np.array([int(x) for x in input().split()])
ans = np.zeros(n, dtype=int)

for i in range(1, n):
	start = max(0, i-k)
	ans[i] = min(ans[start:i] + np.abs(q[i] - q[start:i]))

print(ans[n-1])
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
for i in range(N):
    A_new1 = A[:i] + [0]
    A_new2 = A[i+1:] + [0]
    if max(A_new1) >= max(A_new2):
        print(max(A_new1))
    else:
        print(max(A_new2))


### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A_m = str(max(A))
a = A.index(int(A_m))
A = sorted(A)
if A.count(int(A_m)) >= 2:
    print((A_m + '\n')*(N-1) + A_m)
else:
    print((A_m + '\n')*a + str(A[-2]))
    if N-(a+1) == 1:
        print(A_m)
    elif N-(a+1) < 1:
        pass
    else:
        print((A_m + '\n')*(N-(a+2)) + A_m)
### BUGGY CODE ###

N = int(input())
S = input()
cnt = 0
for i in range(N):
    for j in range(i,N):
        if S[i] != S[j]:
            for k in range(j,N):
                if (S[i] != S[k]) and (S[j] != S[k]) and (j != (i+k)/2):
                    cnt +=1
                else:
                    pass
        else:
            pass
print(cnt)

### FIXED CODE ###

N = int(input())
S = input()
R = S.count("R")
G = S.count("G")
B = S.count("B")
cnt = 0
for i in range(N):
    for j in range(i+1,N):
        if j*2-i < N:
            if (S[i] != S[j]) and (S[i] !=S[(j*2)-i]) and (S[j] != S[(j*2)-i]):
                cnt += 1
            else:
                pass
        else:
            pass
print(R*G*B - cnt)
### BUGGY CODE ###

import sys
from collections import Counter as cc
from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    sys.setrecursionlimit(10**4)
    n = ii()
    a = li()
    c = cc(a)
    N = sum(c.values())
    
    @lru_cache
    def dfs(x, y, z):
        if x== 0 and y == 0 and z == 0:
            return 0
        tmp = 1
        if x > 0:
            tmp += dfs(x-1, y, z)*x/N
        if y> 0:
            tmp += dfs(x+1, y-1, z)*y/N
        if z > 0:
            tmp += dfs(x, y+1, z-1)*z/N
        tmp *= N/(x+y+z)
        return tmp
    
    print(dfs(c[1], c[2], c[3]))

    

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import Counter as cc
from numba import njit
import numpy as np

def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

# sys.setrecursionlimit(10**4)
n = ii()
a = li()
c = cc(a)
N = sum(c.values())
cache = np.full((N+1, N+1, N+1), -1, dtype=float)
cache[0][0][0] = 0
@njit(cache=True)
def dfs(x, y, z, N, cache):
    if x+y+z==0:
        return 0
    if cache[x][y][z]>=0:
        return cache[x][y][z]
    tmp = 1
    if x > 0:
        tmp += dfs(x-1, y, z,N, cache)*x/N
    if y > 0:
        tmp += dfs(x+1, y-1, z, N, cache)*y/N
    if z > 0:
        tmp += dfs(x, y+1, z-1, N, cache)*z/N
    tmp *= N/(x+y+z)
    cache[x][y][z] = tmp
    return tmp

dfs(c[1], c[2], c[3], N, cache)
print(cache[c[1]][c[2]][c[3]])
### BUGGY CODE ###

X = int(input())
a, b = 0, -24
while a**5 - b**5 != X:
    a += 1
    b = -24
    while a**5 - b**5 != X:
        b += 1
print(a, b)


### FIXED CODE ###

def f(X):
    for i in range(1, 120):
        for j in range(-63, 119):
            if i**5 - j**5 == X:
                return i, j
X = int(input())
print(*f(X))
### BUGGY CODE ###

from functools import reduce
from fractions import gcd


def gcd4args(args):
    return reduce(gcd, args)


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

ans = 0
for i in range(N):
    lstTmp = lstA[0:i] + lstA[i+1:]
    ans = max(ans, gcd4args(lstTmp))
print(ans)

### FIXED CODE ###

from fractions import gcd


N = int(input())
lstA = list(map(int, input().split()))
lstL = [0] * N
lstR = [0] * N


for i in range(1, N):
    lstL[i] = gcd(lstL[i-1], lstA[i-1])
for i in range(N-1)[::-1]:
    lstR[i] = gcd(lstR[i+1], lstA[i+1])
lstGcd = [gcd(lstL[i], lstR[i]) for i in range(N)]
ans = max(lstGcd)


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

import numpy as np

MOD = 1000000007;

s = input()

n=len(s)

if n<1 or n>10**5:
	print ('Illegal')
	exit()

#a=[-1]*len(s)
b=np.zeros((n+1, 13), dtype = 'int64')
p=np.zeros(n,dtype=int)

b.shape
p.shape


x=1
for i in reversed(range(n)):
	p[i]=x%13
	x=p[i]*10
	
for i in range(n):
	if(s[i]=="?"):
		c=-1
	else:
		c=int(s[i])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[0][(p[i]*j)%13]=1
		else:
			b[0][(p[i]*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[i][(k+p[i]*j)%13]+=b[i-1][k]
		else:
			for k in range(13):
				b[i][(k+p[i]*c)%13]+=b[i-1][k]

	for k in range(13):b[i][k]%=MOD
#	print (b[i])
#	print (b[i+1])

print (b[n-1][5])


### FIXED CODE ###

MOD = 1000000007;

s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=[0]*13

c=s[0]
if (c!=-1):
	r[c]=1
else:
	for i in range(10):r[i]=1

for i in range(1,n):
	dp=[0]*26
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r=[0]*13
	if (c==-1):
		w=sum(dp[4:14])
		for j in range(13):
				r[j]+=w
				w=w+dp[j+1]-dp[4+j]
	else:
		for j in range(13):
			r[j]+=dp[13-c+j]
print (r[5]%MOD)
### BUGGY CODE ###

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

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

for w in range(M):
    A.sort()
    A[N-1]=A[N-1]/2
    #print(A)

B=list(map(int, A))
#print(B)
print(sum(B))



### FIXED CODE ###

import heapq

N,M=map(int,input().split())
A=list(map(int,input().split()))
#print(A)
A =[-a for a in A]
#print(A)
heapq.heapify(A)

for w in range(M):
    max=heapq.heappop(A)
    heapq.heappush(A,max/2)
   
B=list(map(int, A))
#print(B)
print(sum(B)*-1)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import itertools
sys.setrecursionlimit(10**8)
INF = float("inf")
MOD = 10**9+7

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


AA = [(a, i) for i, a in enumerate(A, start=1)]
AA.sort(reverse=True)
# print(AA)

DP = [[0]*(N+1) for _ in range(N+1)]

for wa in range(1, N+1):
    # AA[:wa]までを考える
    for x in range(wa+1):
        y = wa - x
        a, i = AA[wa-1]
        if x - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x-1][y]+a*(i-x))
        if y - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x][y-1]+a*(N-y-i+1))
        # print(wa, (x, y), (a, i), DP[x][y])

M = -INF
for x in range(N):
    y = N-x
    M = max(DP[x][y], M)
print(M)


# def guchoku():
#     AA = [(a, i) for i, a in enumerate(A)]
#     mt = 0
#     mp = None
#     for p in itertools.permutations(AA):
#         tot = 0
#         for i in range(N):
#             a1, i1 = p[i]
#             tot += a1*abs(i1-i)
#         if mt < tot:
#             mt = tot
#             mp = p
#     return mt, mp


# print(guchoku())


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")
MOD = 10**9+7

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


AA = [(a, i) for i, a in enumerate(A, start=1)]
AA.sort(reverse=True)
# print(AA)

DP = {}
DP[(0, 0)] = 0

for wa in range(1, N+1):
    # AA[:wa]までを考える
    a, i = AA[wa-1]
    for x in range(wa+1):
        y = wa - x
        DP[(x, y)] = 0
        if x - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x-1, y)]+a*(i-x))
        if y - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x, y-1)]+a*(N-y-i+1))
        # print(wa, (x, y), (a, i), DP[x][y])

print(max([DP[(x, N-x)] for x in range(N+1)]))