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

MOD = 1000000007
N = int(input())
A = list(map(int, input().split()))
sum = 0
for i in range(0, N-1):
    A[i] = A[i] % MOD
    for j in range(i+1, N):
        temp3 = 0
        temp3 = (A[i] * A[j]) % MOD
        sum = (sum + temp3) % MOD
print(sum)

### FIXED CODE ###

MOD = 1000000007
N = int(input())
A = list(map(int, input().split()))
ans = 0
B = [0]*(N-1)
sumA = sum(A)
for i in range(1, N):
    sumA -= A[i-1]
    B[i-1] = sumA
for i in range(0, N-1):
    ans += A[i] * B[i]
    ans %= MOD
print(ans)
### BUGGY CODE ###

def main():
    N,K=(int(i) for i in input().split())
    h = [int(i) for i in input().split()]
    c = [0]*N
    for i in range(1,N):
        jumpmax = min(i,K)
        c[i] = min([abs(h[i]-h[i-j])+c[i-j] for j in range(1,jumpmax+1)])
    print(c[N-1])

main()

### FIXED CODE ###

N,K=(int(i) for i in input().split())
h = [int(i) for i in input().split()]
c = [0]*N
for i in range(1,N):
    jumpmax = min(i,K)
    c[i] = min([abs(h[i]-h[i-j])+c[i-j] for j in range(1,jumpmax+1)])
print(c[N-1])
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
count=0
for i in range(1,n):
    if i==1:
        if a[0]>a[1]:
            count+=a[0]-a[1]
    else:
        if max(a[:i])>a[i]:
            count+=max(a[:i])-a[i]
print(count)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
count,max_n=0,a[0]
for i in range(1,n):
    if max_n>a[i]:
        count+=max_n-a[i]
    else:
        max_n=max(max_n,a[i])
print(count)
### BUGGY CODE ###

inp = [int(i) for i in input().split()]
n = inp[0]
a = inp[1]
b = inp[2]

# C = {}
# def cmb(n,r):
#   print(n,r)
#   if r==0 or r ==n:
#     return 1
#   if r==1:
#     return n
#   if (n,r) in C:
#     return C[(n,r)]
#   C[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
#   return C[(n,r)]

# def cmb(n, r):
#     if n - r < r: r = n - r
#     if r == 0: return 1
#     if r == 1: return n
#
#     numerator = [n - r + k + 1 for k in range(r)]
#     denominator = [k + 1 for k in range(r)]
#
#     for p in range(2,r+1):
#         pivot = denominator[p - 1]
#         if pivot > 1:
#             offset = (n - r) % p
#             for k in range(p-1,r,p):
#                 numerator[k - offset] /= pivot
#                 denominator[k] /= pivot
#
#     result = 1
#     for k in range(r):
#         if numerator[k] > 1:
#             result *= int(numerator[k])
#
#     return result

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
M = 10**9
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# for i in range(N+1, )

# mod = 10**9+7
# MAX_N = 10**9

# fact = [1]
# fact_inv = [0]*(MAX_N+4)
# for i in range(MAX_N+3):
#     fact.append(fact[-1]*(i+1)%mod)
#
# fact_inv[-1] = pow(fact[-1],mod-2,mod)
# for i in range(MAX_N+2,-1,-1):
#     fact_inv[i] = fact_inv[i+1]*(i+1)%mod
#
#
# def mod_comb_k(n,k,mod):
#     return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

A = cmb(n,a,mod)
B = cmb(n,b,mod)
ans = 2**n-1-A-B
print(ans%(10**9+7))

### FIXED CODE ###

import math
n,a,b = [int(i) for i in input().split()]
mod = 10**9+7
  
def comb(n,k):
  ans = 1
  for i in range(k):
    ans = ans*(n-i)%mod
  for i in range(1,k+1):
    ans = ans*pow(i,mod-2,mod)%mod
  return ans

print((pow(2,n,mod)-1-comb(n,a)-comb(n,b))%mod)
# print(comb(n,a))
### BUGGY CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# sum_vの取りうる上限値
MAX_V = (10**3+1) * N

# 最小値を求めるので無限大の値
f_inf = float('inf')

def chmin(a, b):
    if a <= b:
        return a
    else:
        return b

def knapsack(n, w):
    # dpの初期化　dp[i][sum_v]は重さの総和の最小値
    dp = [[f_inf for i in range(MAX_V)] for j in range(N+1)]
    # 初期条件
    dp[0][0] = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        w, v = map(int, input().split())
        for sum_v in range(MAX_V):
            # i番目の品物を選ぶ場合
            if (sum_v -v >= 0):
                dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v - v] + w)
            # i番目の品物を選ばない場合
            dp[i + 1][sum_v] = chmin(dp[i + 1][sum_v], dp[i][sum_v])
    #dp[N][sum_v]の値が、W以下であるsum_vの値の最大値
    ans = 0
    for sum_v in range(MAX_V):
        if dp[N][sum_v] <= W:
            ans = sum_v
    print(ans)

knapsack(N, W)




### FIXED CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
# sum_vの取りうる上限値
MAX_V = (10**3) * N +1
# 最小値を求めるので無限大の値
f_inf = float('inf')

def knapsack(n, w):
    # dpの初期化　dp[sum_v]は重さの総和の最小値
    dp = [f_inf] * MAX_V
    # 初期条件
    dp[0] = 0
    sum_v = 0
    # forは全て関数の中で回す。
    # 入力
    for i in range(N):
        w, v = map(int, input().split())
        for j in range(MAX_V, v-1, -1):
            new_weight = dp[j - v] + w
            if new_weight > W:
                continue
            if dp[j] > new_weight:
                dp[j] = new_weight

    ans = 0
    for sum_v in range(MAX_V):
        if dp[sum_v] <= W:
            ans = sum_v
    print(ans)

knapsack(N, W)
### BUGGY CODE ###

N = int(input())
ans = 1
for i in range(N):
    ans *= (i + 1)
print(ans % (10 ** 9 + 7))


### FIXED CODE ###

N = int(input())
ans = 1
for i in range(1, N + 1):
    ans = (i * ans) % (10 ** 9 + 7)
print(ans)
### BUGGY CODE ###

# from itertools import accumulate
n=int(input())
a=list(map(int, input().split()))
# acc=accumulate(a)

cnt=0
for i in range(n):
    # if acc[]-acc[]=
    for j in range(i,n):
        if a[i]+a[j]==j-i:
            cnt+=1
print(cnt)


### FIXED CODE ###

from collections import defaultdict

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

d=defaultdict(int)
ans=0

for i, item in enumerate(a):
    d[i+item]+=1
    ans+=d[i-item]

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

r,g,b,n=map(int,input().split())
ctr=0

num_r=n//r+2
num_g=n//g+2

for i in range(num_r):
    for k in range(num_g):
        if n-r*i-g*k>=0 and (n-r*i-g*k)%b==0:
            ctr+=1
print(ctr)


### FIXED CODE ###

r,g,b,n=map(int,input().split())
ctr=0
l=[r,g,b]
l.sort()
num_1=n//l[2]+1
for i in range(num_1):
    for k in range((n-i*l[2])//l[1]+1):
        if (n-i*l[2]-k*l[1])%l[0]==0:
            ctr+=1
print(ctr)
### BUGGY CODE ###

N = int(input())
A = [0]*N

for n in range(N):
  A[n] = int(input()) -1
  
count = [-1]*N
n = 0
ans = 1
while A[n] != 2-1:
  n = A[n]
  if n in count:
    ans = -1
    break
  count[n] = n
  ans += 1
  
print(ans)

### FIXED CODE ###

n = int(input())
al = []
for i in range(n):
    a = int(input())
    al.append(a)
 
al.insert(0, 0)
ans = -1
push = 1
for i in range(1, n+2):
    light = al[push]
    push = light
    if light == 2:
        ans = i
        break
print(ans)
### BUGGY CODE ###

def main():
    import heapq
    import sys
    input = sys.stdin.buffer.readline
    N, M, L = map(int, input().split())

    G = [[-1]*N for i in range(N)]
    for i in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        G[A][B] = C
        G[B][A] = C

    # ある地点からそこまでにL以下の道があるか、０でいける地点からそのときの残量以下で行ける地点が0で行ける地点
    # ある地点からL以下ではいけるが、その地点に行くまでの残量ではいけない場合には、+1

    D = [[[-1, -1]for j in range(N)] for i in range(N)]
    for i in range(N):
        D[i][i] = [0, L]
    #q = collections.deque()
    hq = []
    count = 0
    for i in range(N):
        r = set([i])
        # q.append(i)
        hq = [(0, i)]
        while(hq):
            count += 1
            #x = q.popleft()
            d, x = heapq.heappop(hq)
            for y in range(N):
                if y not in r and G[x][y] >= 0:
                    if G[x][y] > L:
                        continue
                    elif G[x][y] > D[i][x][1]:
                        if D[i][y][0] == -1 or D[i][y][0] > D[i][x][0]+1:
                            D[i][y][0] = D[i][x][0] + 1
                            D[i][y][1] = L - G[x][y]
                            heapq.heappush(hq, (D[i][y][0], y))
                        elif D[i][y][0] == D[i][x][0]+1 and D[i][y][1] < L - G[x][y]:
                            D[i][y][1] = L - G[x][y]
                            heapq.heappush(hq, (D[i][y][0], y))
                    else:
                        if D[i][y][0] == -1 or D[i][y][0] > D[i][x][0]:
                            D[i][y][0] = D[i][x][0]
                            D[i][y][1] = D[i][x][1] - G[x][y]
                            heapq.heappush(hq, (D[i][y][0], y))
                        elif D[i][y][0] == D[i][x][0] and D[i][y][1] < D[i][x][1] - G[x][y]:
                            D[i][y][1] = D[i][x][1] - G[x][y]
                            heapq.heappush(hq, (D[i][y][0], y))
    # print(D)

    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        print(D[s][t][0])


main()


### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra


def main():
    import heapq
    import sys
    input = sys.stdin.buffer.readline
    N, M, L = map(int, input().split())

    G = [[-1]*N for i in range(N)]

    for i in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        G[A][B] = C
        G[B][A] = C
    g = csgraph_from_dense(G, null_value=-1)
    D = dijkstra(g)
    G2 = [[-1]*N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if D[i][j] >= 0 and D[i][j] <= L:
                G2[i][j] = 1

    g2 = csgraph_from_dense(G2, null_value=-1)
    D = dijkstra(g2)


    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if D[s][t] <= N**2:
            print(int(D[s][t])-1)
        else:
            print(-1)


main()
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0
rgb_idx = {
    'R': [],
    'G': [],
    'B': [],
}
for i in range(n):
    if s[i] == 'R':
        rgb_idx['R'].append(i)
    elif s[i] == 'G':
        rgb_idx['G'].append(i)
    else:
        rgb_idx['B'].append(i)

for i in range(len(rgb_idx['R'])):
    for j in range(len(rgb_idx['G'])):
        ans += len(rgb_idx['B'])
        rnum = rgb_idx['R'][i]
        gnum = rgb_idx['G'][j]
        if gnum-rnum>0:
            g = gnum
            l = rnum
        else:
            g = rnum
            l = gnum
        if g+abs(gnum-rnum) in rgb_idx['B']:
            ans -= 1
        if l-abs(gnum-rnum) in rgb_idx['B']:
            ans -= 1
        if (g+l)/2 in rgb_idx['B']:
            ans -= 1

print(ans)


### FIXED CODE ###

n = int(input())
s = input()

ans = 0
rgb_idx = {
    'R': [],
    'G': [],
    'B': [],
}
for i in range(n):
    if s[i] == 'R':
        rgb_idx['R'].append(i)
    elif s[i] == 'G':
        rgb_idx['G'].append(i)
    else:
        rgb_idx['B'].append(i)

for i in range(len(rgb_idx['R'])):
    for j in range(len(rgb_idx['G'])):
        ans += len(rgb_idx['B'])
        
        rnum = rgb_idx['R'][i]
        gnum = rgb_idx['G'][j]
        if gnum-rnum>0:
            g = gnum
            l = rnum
        else:
            g = rnum
            l = gnum
        dist = abs(gnum-rnum)
        if n > g+dist and s[g+dist]=='B':
            ans -= 1
        if 0 <= l-dist and s[l-dist]=='B':
            ans -= 1
        if (g+l)%2==0 and s[int((g+l)/2)]=='B':
            ans -= 1

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

N = int(input())
s_list = []
for i in range(N):
    s_list.append(input())

def strcount(string):
    dic = {}
    for s in string:
        if s not in dic:
            dic[s] = 1
        else:
            dic[s] += 1
    return dic

cnt = 0
for i in range(N):
    dic = strcount(s_list[i])
    for j in range(i + 1, N):
        #dic = strcount(s_list[i])
        if dic == strcount(s_list[j]):
            cnt += 1
print(cnt)


### FIXED CODE ###

N = int(input())
anagram = {}

ans = 0
for i in range(N):
    tmp = str(sorted(input()))
    if tmp in anagram:
        ans += anagram[tmp]
        anagram[tmp] += 1
    else:
        anagram[tmp] = 1

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

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

use = [i for i in range(10)]

for _d in d:
    use.remove(_d)

ok = True

while True:
    s = list(str(n))
    for _d in d:
        if str(_d) in s:
            ok = False
            break
    
    if ok:
        print(n)
        exit()
    else:
        n += 1



### FIXED CODE ###

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

use = [i for i in range(10)]

for _d in d:
    use.remove(_d)


while True:
    ok = True
    s = str(n)
    for i in range(len(s)):
        if int(s[i]) not in use:
            ok = False
            break

    if ok:
        print(n)
        exit()
    else:
        n += 1
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
hyouten=[0]*(N+5)

hyouten[K-1]=A[0]
for i in range(1,K):
    hyouten[K-1]*=A[i]

for i in range(K,N):
    hyouten[i]=hyouten[i-1]*A[i]/A[i-K]



for i in range(K,N):

    if hyouten[i] > hyouten[i-1]:
        # print(hyouten[i-1],hyouten[i])
        print("Yes")
    else:
        # print(hyouten[i-1],hyouten[i])
        print("No")
    


### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(0,N-K):
    if A[i]< A[i+K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from bisect import bisect_left
a,b,q = map(int, input().split())
S = []
for _ in range(a):
  S.append(int(input()))
T = []
for _ in range(b):
  T.append(int(input()))
X = []
for _ in range(q):
  X.append(int(input()))

INF = 10 ** 11
def dfs(direction, tors, pos, count):
  if tors == 1:
    L = T
  elif tors == -1:
    L = S
  i = bisect_left(L, pos)
  if i == len(L):
    if direction == 1:
      return INF
    elif direction == -1:
      res = abs(L[i-1]-pos)
      next_pos = L[i-1]
  elif L[i] == pos:
    res = 0
    next_pos = pos
  else:
    if direction == 1:
      res = abs(L[i]-pos)
      next_pos = L[i]
    elif direction == -1:
      if i == 0:
        return INF

      res = abs(L[i-1]-pos)
      next_pos = L[i-1]

  if count == 1:
    return res

  res0 = res + dfs(direction, tors*(-1), next_pos, count-1)
  res1 = res + dfs(direction*(-1), tors*(-1), next_pos, count-1)

  return min(res0, res1)

for x in X:
  res0 = dfs(1, 1, x, 2)
  res1 = dfs(-1, 1, x, 2)
  res2 = dfs(1, -1, x, 2)
  res3 = dfs(-1, -1, x, 2)

  print(min(res0, res1, res2, res3))


### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = INF
  for S in [s[b - 1], s[b]]:
    for T in [t[d - 1], t[d]]:
      d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
      res = min(res, d1, d2)
  print(res)
### BUGGY CODE ###

a, b, c, k = map(int, input().split())
if a == b == c:
    print(0)
    exit()
for i in range(k):
    tmp1 = a+b
    tmp2 = b+c
    tmp3 = c+a
    a = tmp2
    b = tmp3
    c = tmp1
    if a-b > 10**18:
        print('Unfair')
        exit()
print(a-b)


### FIXED CODE ###

a, b, c, k = map(int, input().split())
if a == b == c:
    print(0)
elif a-b > 10**18:
    print('Unfair')
else:
    if k % 2 == 0:
        print(a-b)
    else:
        print(b-a)
### BUGGY CODE ###

N = int(input())
move = []
for i in range(N):
    X,L = map(int,input().split())
    move.append([X-L,X+L])
move = sorted(move, key=lambda x:(x[0],x[1]))

if N == 1:
    print(1)
else:    
    i = 1
    while(len(move) > i):
        if move[i-1][0] == move[i][0]:
            del move[i-1]
        else:
            if move[i][1] <= move[i-1][1]:
                del move[i]
            else:
                i += 1
    
    if len(move) <= 2:
        print(len(move))
    else:
        i = 1
        while(len(move) > i+1):
            if move[i-1][1] >= move[i+1][0]:
                del move[i]
            else:
                i += 1
        print(len(move))

### FIXED CODE ###

N = int(input())
K = []
for i in range(N):
    X,L = map(int,input().split())
    K.append([X-L,X+L])

T = sorted(K,key=lambda x:x[1])
a = T[0][1]

c = 1
for i in range(1,N):
    if T[i][0] >= a:
        c += 1
        a = T[i][1]
print(c)
### BUGGY CODE ###

S = list(str(input()))
S = [int(s) for s in S]
n = len(S)

S.reverse()

cum1 = [-1]*(n+1)
cum1[0] = 0
for i in range(n):
    temp = cum1[i]+S[i]*10**i
    cum1[i+1] = temp%673
#print(cum1)

cum2 = [-1]*(n+1)
cum2[0] = 0
for i in range(n):
    temp = cum2[i]+S[i]*10**i
    cum2[i+1] = temp%3
#print(cum2)

d = {}
ans = 0
for i in range(n+1):
    c1 = cum1[i]
    c2 = cum2[i]
    if (c1, c2) in d:
        ans += d[(c1, c2)]
        d[(c1, c2)] += 1
    else:
        d[(c1, c2)] = 1
print(ans)


### FIXED CODE ###

S = list(str(input()))
S = [int(s) for s in S]
n = len(S)

S.reverse()

def power(a, n, mod):
  bi=str(format(n,"b")) #2進数
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

cum1 = [-1]*(n+1)
cum1[0] = 0
for i in range(n):
    temp = cum1[i]+S[i]*power(10, i, 673)
    cum1[i+1] = temp%673
#print(cum1)

cum2 = [-1]*(n+1)
cum2[0] = 0
for i in range(n):
    temp = cum2[i]+S[i]*power(10, i, 3)
    cum2[i+1] = temp%3
#print(cum2)

d = {}
ans = 0
for i in range(n+1):
    c1 = cum1[i]
    c2 = cum2[i]
    if (c1, c2) in d:
        ans += d[(c1, c2)]
        d[(c1, c2)] += 1
    else:
        d[(c1, c2)] = 1
print(ans)
### BUGGY CODE ###

import fractions as f 
a=int(input())
ans=0
for i in range(1,a+1):
 for j in range(1,a+1):
  for k in range(1,a+1):
   b=f.gcd(i,j)
   ans+=f.gcd(b,k)
print(ans)

### FIXED CODE ###

import math as f 
a=int(input())
ans=0
for i in range(1,a+1):
 for j in range(1,a+1):
  for k in range(1,a+1):
   b=f.gcd(i,j)
   ans+=f.gcd(b,k)
print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
hc = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            hc[i][j] = hc[i][j - 1] + 1
for i in range(h):
    for j in range(w - 1, -1, -1):
        if s[i][j] == ".":
            if j < w - 1:
                if hc[i][j] < hc[i][j + 1]:
                    hc[i][j] = hc[i][j + 1]
wc = [[0] * h for i in range(w)]
for i in range(w):
    for j in range(h):
        if s[j][i] == ".":
            wc[i][j] = wc[i][j - 1] + 1
for i in range(w):
    for j in range(h - 1, -1, -1):
        if s[j][i] == ".":
            if j < h - 1:
                if wc[i][j] < wc[i][j + 1]:
                    wc[i][j] = wc[i][j + 1]
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, hc[i][j] + wc[j][i] - 1)
print(ans)

### FIXED CODE ###

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
hc = [[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            if j > 0:
                hc[i][j] = hc[i][j - 1] + 1
            else:
                hc[i][j] = 1
for i in range(h):
    for j in range(w - 1, -1, -1):
        if s[i][j] == ".":
            if j < w - 1:
                if hc[i][j] < hc[i][j + 1]:
                    hc[i][j] = hc[i][j + 1]
wc = [[0] * h for i in range(w)]
for i in range(w):
    for j in range(h):
        if s[j][i] == ".":
            if j > 0:
                wc[i][j] = wc[i][j - 1] + 1
            else:
                wc[i][j] = 1
for i in range(w):
    for j in range(h - 1, -1, -1):
        if s[j][i] == ".":
            if j < h - 1:
                if wc[i][j] < wc[i][j + 1]:
                    wc[i][j] = wc[i][j + 1]
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, hc[i][j] + wc[j][i] - 1)
print(ans)
### BUGGY CODE ###

x=int(input())
for i in range(1,int(x**(1/2))+1):
    if x%i:continue

    ar,s=i,x//i
    pre=[]
    if pow(ar,5,5)==x%5:pre.append(ar)
    if  pow(s,5,5)==x%5:pre.append(s)

    for a in set(pre):
        d=(x-a**5)//5//a
        if d==0:print(a,0);exit()
        for b in range(1,int(abs(d)**(1/2))+1):
            if d%b:continue
            if (a+b)**5-b**5==x:
                print(a+b,b);exit()
            if (a-b)**5+b**5==x:print(a-b,-b);exit()

### FIXED CODE ###

x=int(input())
for i in range(-120,121):
  for j in range(-120,121):
    if pow(i,5)-pow(j,5)==x:
      print(i,j);exit()
### BUGGY CODE ###

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

def calc_exp(n):
    exp=1+(n-1)*0.5
    return exp

for i,val in enumerate(p):
    p[i]=calc_exp(val)

ans=0
for i in range(n-k+1):
    ans=max(ans,sum(p[i:i+k]))
print(ans)

### FIXED CODE ###

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

def calc_exp(n):
    exp=1+(n-1)*0.5
    return exp

tmp=sum(p[:k])
mx=tmp
ind=0
for i in range(1,n-k+1):
    # tmp=sum(p[i:i+k])
    tmp-=p[i-1]
    tmp+=p[i+k-1]
    if mx<tmp:
        ind=i
        mx=tmp
        
ans=0
for i in range(k):
    ans+=1+(p[ind+i]-1)*0.5
    
print(ans)
### BUGGY CODE ###

import resource
import sys
from functools import lru_cache
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.reverse()
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def f(k, p):
  for a in A:
    if k >= a:
      if f(k-a, p ^ 1) == p:
        return p
  return p ^ 1

print('First' if f(K, 0) == 0 else 'Second')


### FIXED CODE ###

import resource
import sys
from functools import lru_cache
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.reverse()
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def f(k, p):
  for a in A:
    if k >= a:
      if f(k-a, p ^ 1) == p:
        return p
  return p ^ 1

print('First' if f(K, 0) == 0 else 'Second')
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: x[1])

dp = [[0] * (N+1) for _ in range(N+1)]
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        idx, a = arridx[i]
        lsc = rsc = 0
        if l > 0:
            # l-1, r から
            lsc = dp[l-1][r] + a * abs(l-1-idx)
        if r < N-1:
            # l, r+1 から
            rsc = dp[l][r+1] + a * abs(r+1-idx)
        dp[l][r] = max(lsc, rsc)
print(max(dp[i][i-1] for i in range(N)))

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: x[1])

dp = {}
dp[(0, N-1)] = 0
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        idx, a = arridx[i]
        lsc = rsc = 0
        if l > 0:
            # l-1, r から
            lsc = dp[(l-1, r)] + a * abs(l-1-idx)
        if r < N-1:
            # l, r+1 から
            rsc = dp[(l, r+1)] + a * abs(r+1-idx)
        ndp[(l, r)] = max(lsc, rsc)
    dp = ndp
print(max(dp.values()))
### BUGGY CODE ###

s = input()
ans = ''
for i in range(len(s)):
    if s[i] == "?":
        ans += "D"
    else:
        ans += s[i]
print(ans)

### FIXED CODE ###

s = input()
print(s.replace('?', 'D'))
### BUGGY CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline
import numpy as np

def main():
    numbers=[]
    n = int(input())
    numbers=np.array(list(map(int,input().split())))

    for i in range(n):
        if i==0:
            left=numbers[:i].sum()
            right=numbers[i:].sum()
            continue
        else:
            if abs(right-left) > abs(numbers[i:].sum() -numbers[:i].sum()):
                left=numbers[:i].sum()
                right=numbers[i:].sum()
    print(abs(right-left))


if __name__=="__main__":
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline
import numpy as np

def main():
    N=[]
    n = int(input())
    N=np.array(list(map(int,input().split())))
    Ncum=N.cumsum()
    L=Ncum[:-1]
    R=Ncum[-1]-L
    ans=np.abs(L-R).min()
    print(ans)

if __name__=="__main__":
    main()