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

import sys
input = sys.stdin.readline
def print_ans(N, sr):
    """Test Case
    >>> print_ans(3, ["acornistnt", "peanutbomb", "constraint"])
    1
    >>> print_ans(2, ["oneplustwo", "ninemodsix"])
    0
    >>> print_ans(5,["abaaaaaaaa","oneplustwo","aaaaaaaaba","twoplusone","aaaabaaaaa"]) 
    4
    """
    for i in range(N):
        sr[i] = "".join(sorted(sr[i]))
    count = 0
    for i in range(N):
        tmp = sr[i]
        for k in range(i + 1, N):
            if tmp == sr[k]:
                count +=1
    print(count)


if __name__ == '__main__':
    N = int(input().rstrip())
    sr = [ input().rstrip() for _ in range(N)]
    print_ans(N, sr)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
def print_ans(N, sr):
    """Test Case
    >>> print_ans(3, ["acornistnt", "peanutbomb", "constraint"])
    1
    >>> print_ans(2, ["oneplustwo", "ninemodsix"])
    0
    >>> print_ans(5,["abaaaaaaaa","oneplustwo","aaaaaaaaba","twoplusone","aaaabaaaaa"]) 
    4
    """
    for i in range(N):
        sr[i] = "".join(sorted(sr[i]))
    C = Counter(sr)
    ans = 0
    for v in C.values():
        ans += v * (v - 1) // 2
    print(ans)

    # for i in range(N):
    #     tmp = sr[i]
    #     for k in range(i + 1, N):
    #         if tmp == sr[k]:
    #             count +=1
    # print(count)


if __name__ == '__main__':
    N = int(input().rstrip())
    sr = [ input().rstrip() for _ in range(N)]
    print_ans(N, sr)
### BUGGY CODE ###

n = int(input())
l = input().split()

for i in range(0,n):
	l[i] = int(l[i])

counting = 0
list_i = []
set_l = set(l)
max_counting = 0
for i in set_l:
	counting = 0
	for j in range(n):
		if (l[j] == i or l[j] == i-1 or l[j] == i+1):
			counting += 1		
	if max_counting < counting:
		max_counting = counting
			 
print(max_counting)

### FIXED CODE ###

n = int(input())
l = input().split()

for i in range(0,n):
	l[i] = int(l[i])

dict_i = {}
for i in range(-1,100001):
	dict_i[i] = 0
	
for j in range(n):
	dict_i[l[j]] += 1
	dict_i[l[j] + 1] += 1
	dict_i[l[j] - 1] += 1
print(max(dict_i.values()))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]

for _ in range(M):
	a, b = map(int, input().split())
	friend[a - 1].append(b - 1)
	friend[b - 1].append(a - 1)
	
for _ in range(K):
	c, d = map(int, input().split())
	block[c - 1].append(d - 1)
	block[d - 1].append(c - 1)
	
# 同じ連結成分にラベルを振る（まだラベルを振っていない = -1 で初期化）
label = [-1] * N

cnt_label_num = 0

for i in range(N):
	if label[i] != -1: continue # もう振ってあったら飛ばす
	
	# 振ってなかったら幅優先でラベルを振る
	Q = [i]
	while Q:
		cur = Q.pop(0)
		if label[cur] != -1: continue
		label[cur] = cnt_label_num
		for adj in friend[cur]:
			if label[adj] != -1: continue
			Q.append(adj)
	
	cnt_label_num += 1
	
# お友達候補計算
cnt = Counter(label)
for i in range(N):
	friend_candidate = cnt[label[i]] - 1 # 同じグラフにいる人
	friend_candidate -= len(friend[i]) # 元から友達を引く
	# blockしている人が同じグラフにいるときはその分引く
	for block_man in block[i]:
		if label[i] == label[block_man]:
			friend_candidate -= 1
	print(friend_candidate, end = " ")

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter
N, M, K = map(int, input().split())
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]

for _ in range(M):
	a, b = map(int, input().split())
	friend[a - 1].append(b - 1)
	friend[b - 1].append(a - 1)
	
for _ in range(K):
	c, d = map(int, input().split())
	block[c - 1].append(d - 1)
	block[d - 1].append(c - 1)
	
# 同じ連結成分にラベルを振る（まだラベルを振っていない = -1 で初期化）
label = [-1] * N

cnt_label_num = 0

for i in range(N):
	if label[i] != -1: continue # もう振ってあったら飛ばす
	
	# 振ってなかったら幅優先でラベルを振る
	Q = [i]
	while Q:
		cur = Q.pop()
		if label[cur] != -1: continue
		label[cur] = cnt_label_num
		for adj in friend[cur]:
			if label[adj] != -1: continue
			Q.append(adj)
	
	cnt_label_num += 1
	
# お友達候補計算
cnt = Counter(label)
for i in range(N):
	friend_candidate = cnt[label[i]] - 1 # 同じグラフにいる人
	friend_candidate -= len(friend[i]) # 元から友達を引く
	# blockしている人が同じグラフにいるときはその分引く
	for block_man in block[i]:
		if label[i] == label[block_man]:
			friend_candidate -= 1
	print(friend_candidate, end = " ")
### BUGGY CODE ###

#H = int(input())
H,N = list(map(int,input().split()))
#H = sorted(list(map(int,input().split())))
AB = [list(map(int,input().split())) for i in range(N)]
dp = [[float('inf') for i in range(H)] for j in range(N)]
for i in range(N):
    dp[i][0] = 0
for j in range(H):
    if j-AB[0][0] >= 0:
        dp[0][j] = dp[0][j-AB[0][0]]+AB[0][1]
for i in range(1,N):
    for j in range(H):
        if j-AB[i-1][0] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-AB[i-1][0]]+AB[i-1][1])
        if j-AB[i][0] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i][j-AB[i][0]]+AB[i][1])

ans = float('inf')
for i in range(N):
    for j in range(max(0,H-AB[i][0]),H):
        if dp[-1][j] != float('inf') and j+AB[i][0] >= H:
            ans = min(ans,dp[-1][j]+AB[i][1])
print(ans)

### FIXED CODE ###

#H = int(input())
H,N = list(map(int,input().split()))
#H = sorted(list(map(int,input().split())))
AB = sorted([list(map(int,input().split())) for i in range(N)])
dp = [float('inf') for i in range(H)]
dp[0] = 0
for i in range(N):
    for j in range(H):
        if j-AB[i][0] >= 0:
            dp[j] = min(dp[j],dp[j-AB[i][0]]+AB[i][1])
ans = float('inf')
for i in range(N):
    for j in range(max(0,H-AB[i][0]),H):
        if dp[j] != float('inf') and j+AB[i][0] >= H:
            ans = min(ans,dp[j]+AB[i][1])
print(ans)
### BUGGY CODE ###

import bisect

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

for _ in range(M):
    ins = A.pop() // 2
    A.insert(bisect.bisect_left(A, ins), ins) 

print(sum(A))

### FIXED CODE ###

import heapq

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

for _ in range(M):
    high = -heapq.heappop(A)
    heapq.heappush(A, -(high//2))

print(-sum(A))
### BUGGY CODE ###

#!/usr/bin/env python3
import bisect 
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
for i in range(m):
    a[-1]=a[-1]//2
    a.sort()
print(sum(a))

### FIXED CODE ###

#!/usr/bin/env python3
import bisect 
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
count=0
while True:
    a.sort(reverse=True)
    a0=a[0]//2
    for i in range(n):
        a[i]=a[i]//2
        count+=1
        if count==m:
            print(sum(a))
            exit()
        if i==n-1:break
        if a[i+1]<a0:
            break
### BUGGY CODE ###

H, W, M = map(int, input().split())
HW_L = [[int(x)-1 for x in input().split()] for y in range(M)]

w_l = [0] * W
h_l = [0] * H

for _hi, _wi in HW_L:
    w_l[_wi] += 1
    h_l[_hi] += 1

max_h = max(h_l)
max_w = max(w_l)

h_idx = [i for i, x in enumerate(h_l) if x == max_h]
w_idx = [i for i, x in enumerate(w_l) if x == max_w]

ans = max_h + max_w - 1

for hi in h_idx:
    for wj in w_idx:
        if [hi, wj] not in HW_L:
            ans = max_h + max_w
            break
    else:
        continue
    break

print(ans)


### FIXED CODE ###

H, W, M = map(int, input().split())
HW_L = set(tuple(int(x)-1 for x in input().split()) for y in range(M))

w_l = [0] * W
h_l = [0] * H

for _hi, _wi in HW_L:
    w_l[_wi] += 1
    h_l[_hi] += 1

max_h = max(h_l)
max_w = max(w_l)

h_idx = [i for i, x in enumerate(h_l) if x == max_h]
w_idx = [i for i, x in enumerate(w_l) if x == max_w]

ans = max_h + max_w - 1

for hi in h_idx:
    for wj in w_idx:
        if (hi, wj) not in HW_L:
            ans = max_h + max_w
            break
    else:
        continue
    break

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


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

cnt = 0
for i in range(N-1): 
  for j in range(i+1,N):
    cnt += A[i] * A[j]

print(cnt%(10**9+7))

### FIXED CODE ###

#Sが長いほう
N = int(input())
A = list(map(int, input().split()))

cnt = 0
sumall = sum(A)
#print(sumall)
for i in range(N-1):
  sumall -= A[i]
  cnt += (A[i] * sumall )%(10**9+7)
print(cnt%(10**9+7))
### BUGGY CODE ###

n, k = map(int, input().split())
l = [_ for _ in range(n + 1)]

from itertools import combinations

x = []
y = []
z = 0
for i in range(k, n+2):
    x = list(combinations(l, i))
    for j in range(len(x)):
        y.append(sum(x[j]))
    z += len(set(y)) % (10**9+7)
    x,y = [],[]

print(z)


### FIXED CODE ###

n, k = map(int, input().split())
l = [_ for _ in range(n + 1)]

tmp_min = sum(l[0:k])
tmp_max = sum(l[-1:-k-1:-1])
x = tmp_max - tmp_min + 1

for i in range(n-k+1):
    tmp_min += l[k+i]
    tmp_max += l[-k-i-1]
    x += tmp_max - tmp_min + 1

print(x % (10**9+7))
### BUGGY CODE ###

# DFS
from collections import deque
N, M, Q = map(int, input().split())
ls = []
for i in range(Q):
    ls.append([int(j) for j in input().split()])
arr = list(range(1, M+1))
ans = 0
for i in range(1, M+1):
    st = deque([])
    st.append((i, str(i)))
    while st:
        p, l = st.pop()
        if len(l) == N:
            cur = 0
            for y in ls:
                if int(l[y[1]-1]) - int(l[y[0]-1]) == y[2]:
                    cur += y[3]
            ans = max(ans, cur)
        else:
            for j in range(p, M+1):
                st.append((j, l + str(j)))
print(ans)

### FIXED CODE ###

# 数列生成
from itertools import combinations
N, M, Q = map(int, input().split())
ls = []
for i in range(Q):
    ls.append([int(j) for j in input().split()])
V = [[] for i in range(N+1)]
for i in range(1, M+1):
    V[1].append([i])

for i in range(1, N):
    for v in V[i]:
        b = v[-1]
        for x in range(b, M+1):
            V[i+1].append(v + [x])
ans = 0
for x in V[-1]:
    cur = 0
    for z in ls:
        if x[z[1]-1] - x[z[0]-1] == z[2]:
            cur += z[3]
    ans = max(ans, cur)
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
R = S.count('R')
G = S.count('G')
B = S.count('B')
ans = R * G * B
for d in range(1, N):
  for i in range(N):
    j = i + d
    k = i + d + d
    if k < N and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
      ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
R = S.count('R')
G = S.count('G')
B = S.count('B')
ans = R * G * B
for d in range(1, N):
  for i in range(N):
    j = i + d
    k = i + d + d
    if k < N and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
      ans -= 1
print(ans)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    cards = list(range(1, N + 1))
    for i in range(M):
        L, R = map(int, input().split())
        cards = [x for x in cards if L <= x <= R]
    print(len(cards))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    L, R = 0, 1001001
    for i in range(M):
        l, r = map(int, input().split())
        L = max(L, l)
        R = min(r, R)
    print(max(0, R - L + 1))


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

n = int(input())
def fib(n):
    if (n == 0 or n == 1):
        return 1
    return fib(n-1) + fib(n-2)
print(fib(n))


### FIXED CODE ###

n = int(input())
f = [1,1]
for i in range(n-1):
    fib = f[-1] + f[-2]
    f.append(fib)
print(f[n])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 998244353

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

s = []
for _ in range(k):
    l, r = map(int, input().split())
    s += list(range(l, r+1))

s = set(s)

dp = [0] * (2 * n)
dp[0] = 1

s = sorted(list(s))


for i in range(n):
    if dp[i] == 0:
        continue
    for s_ele in s:
        if s_ele + i > n:
            break
        dp[i+s_ele] += dp[i]

print(dp[n-1]%mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 998244353

n, k = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n+1)
dp[1] = 1

for i in range(1, n):
    dp[i+1] += dp[i]
    for l, r in lr:
        dp[i+1] += dp[max(i-l+1, 0)] - dp[max(i-r, 0)]
        dp[i+1] %= mod

print((dp[n]-dp[n-1])%mod)
### BUGGY CODE ###

def main():

    k = int(input())
    if k % 2 == 0:
        print('-1')
    else:
        for i in range(1, k + 1):
            target = int('1' * i) * 7
            if target % k == 0:
                print(i)
                break

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():

    k = int(input())
    a = [0] * (10 ** 6 + 1)
    a[0] = 7 % k
    if a[0] == 0:
        print(1)
        exit()
    for i in range(1, k + 1):
        a[i] = (a[i - 1] * 10 + 7) % k
        if a[i] == 0:
            print(i + 1)
            exit()
    print(-1)

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

n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    S = s[l-1:r]
    ans = S.count('AC')
    print(ans)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ls = [0] * n
cnt = 0
for i in range(1, n):
    if s[i] == 'C' and s[i-1] == 'A':
        cnt += 1
    ls[i] += cnt
for j in range(q):
    l, r = map(int, input().split())
    print(ls[r-1]-ls[l-1])
### BUGGY CODE ###

s = input()
mod = 10**9 + 7
dp = [[0]*13 for i in range(len(s)+1)]
dp[0][0] = 1
for i in range(len(s)):
    for j in range(13):
        if s[i] != '?':
            dp[i + 1][(j*10 + int(s[i]))%13] += dp[i][j]
            dp[i + 1][(j*10 +int(s[i]))%13] %= mod
        else:
            for k in range(10):
                dp[i + 1][(j*10 + k) % 13] += dp[i][j]
                dp[i + 1][(j*10 + k) % 13] %= mod
print(dp[len(s)][5]%mod)



### FIXED CODE ###

s = input()
mod = 10**9 + 7
dp = [[0]*13 for i in range(len(s)+1)]
dp[0][0] = 1
for i in range(len(s)):
    for j in range(13):
        if s[i] != '?':
            dp[i + 1][(j*10 + int(s[i]))%13] += dp[i][j]
            dp[i + 1][(j*10 +int(s[i]))%13] %= mod
        else:
            for k in range(10):
                dp[i + 1][(j*10 + k) % 13] += dp[i][j]
                dp[i + 1][(j*10 + k) % 13] %= mod
print(dp[len(s)][5]%mod)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

b = set(sorted(a))
count = 0

for i in b:
    if a.count(i) % 2 == 0:
        pass
    else:
        count += 1

print(count)

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

a = sorted(a)
tmp = 0
ans = 0
for i in a:
    if i == tmp:
        ans -= 1
        tmp = 0
    else:
        ans += 1
        tmp = i

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

msg=input()
while True:
    msg=msg.replace("ST","")
    if msg.count("ST")==0:
        break
print(len(msg))


### FIXED CODE ###

ipt = raw_input()
l = ""
for s in ipt:
    if not l:
        l += s
    elif l[-1]+s == "ST":
        l = l[:-1]
    else:
        l += s
print len(l)
### BUGGY CODE ###

def main():
    A = input()[::-1]
    A = "0" + A
    # lis_num = [int(s) for s in A]

    # print(lis_num)

    # S = [0] * len(lis_num)
    S = [0] * len(A)
    cnt = [0] * 2019
    cnt[0] = 1

    for i in range(len(A) - 1):
        S[i + 1] = (S[i] + int(A[i + 1]) * pow(10, i)) % 2019
        cnt[S[i + 1] % 2019] += 1

    # print(S)

    # for i in S:
    #     cnt[i % 2019] += 1

    ans = 0

    for i in range(2019):
        ans += cnt[i] * (cnt[i] - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    A = input()[::-1]
    A = "0" + A
    # lis_num = [int(s) for s in A]

    # print(lis_num)

    # S = [0] * len(lis_num)
    S = [0] * len(A)
    cnt = [0] * 2019
    cnt[0] = 1

    for i in range(len(A) - 1):
        S[i + 1] = (S[i] + int(A[i + 1]) * pow(10, i, 2019)) % 2019
        cnt[S[i + 1] % 2019] += 1

    # print(S)

    # for i in S:
    #     cnt[i % 2019] += 1

    ans = 0

    for i in cnt:
        ans += i * (i - 1) // 2

    print(ans)


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

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def combination_to_index(a,b,n):
    if(b<a):
        c = a
        a = b
        b = c
    return (2*n-a)*(a-1)//2+b-a

def dfs(gp):
    max_d = 0
    stk = []
    stk.append((0,set(),0))
    while stk:
        nxt = []
        n,seen,d = stk.pop()
        res = -1
        if(n in seen):
            continue
        max_d = max(max_d,d)
        for x in gp[n]:
            nxt.append((x,seen.union(set([n])),d+1))
        stk = nxt+stk
    return max_d

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            gp[combination_to_index(a,b,N)].append(combination_to_index(a,A[ind+1],N))
    cnts = [0]*(M+1)
    for i in gp:
        for j in i:
            cnts[j]+=1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)

    d = dfs(gp)
    if(d==0):
        print(-1)
    else:
        print(d)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
def combination_to_index(a,b,n):
    if(b<a):
        a,b = b,a
    return (2*n-a)*(a-1)//2+b-a

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    cnts = [0]*(M+1)
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            fr = combination_to_index(a,b,N)
            to = combination_to_index(a,A[ind+1],N)
            gp[fr].append(to)
            cnts[to] += 1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)
            cnts[ind]+=1

    ans = 0
    cnt = 0
    stk = deque()
    stk.append((0,0))
    while stk:
        n,ans = stk.popleft()
        for x in gp[n]:
            cnts[x]-=1
            if(cnts[x]==0):
                stk.append((x,ans+1))
                cnt += 1
    if(cnt!=M):
        print(-1)
    else:
        print(ans)

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

from itertools import chain


def f(s):
    l = s.split('01')
    for i in range(len(l)):
        l[i] = l[i].split('10')
    l = list(chain.from_iterable(l))
    return l


s = input().rstrip()

count = 0
while True:
    l = f(s)
    if len(l) == 1:
        break
    count += (len(l) - 1) * 2
    s = ''.join(l)

print(count)


### FIXED CODE ###

s = input().rstrip()

print(2 * min(s.count('0'), s.count('1')))
### BUGGY CODE ###

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

AB = [list(map(int, input().split())) for _ in range(N)]

d = [0] + [10 ** 18] * H

for hp in range(1, H + 1):
    for ab in AB:
        # print(ab)
        hp_remain = hp - ab[0]
        if hp_remain < 0: hp_remain = 0
        # print(hp_remain)
        c = d[hp_remain] + ab[1]
        if c < d[hp]: d[hp] = c

print(d[H])




### FIXED CODE ###

import numpy as np


H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
a, b = np.array(AB, dtype=np.int64).reshape(N, 2).T

d = np.zeros(H + 1, dtype=np.int64)

for hp in range(1, H + 1):
    c = d[np.maximum(hp - a, 0)] + b
    d[hp] = np.amin(c)

print(d[H])
### BUGGY CODE ###

S = list(input())
count = 0

for i in range(len(S)-3):
    for j in range(i+4, len(S)+1):
        num = int(''.join(S[i:j]))
        if num % 2019 == 0:
            count += 1

print(count)


### FIXED CODE ###

S = list(input())[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1  # If 2019 is exist, count number
current = 0
x = 1
for s in S:
    current = (current + x * int(s)) % 2019
    ans += mods[current]
    mods[current] += 1
    x = x * 10 % 2019

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

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

def add_one(x):
    return x + 1

w_counter_before = [0] * n
w_counter_all = 0
for i in range(n):
    if s[i] == '.': # white
        w_counter_before[i:] = list(map(add_one, w_counter_before[i:]))
        w_counter_all += 1

if w_counter_all == 0:
    print(0)
else:
    counters = []
    for i in range(n):
        cost1 = i - w_counter_before[i] + 1
        cost2 = w_counter_all - w_counter_before[i]
        counters.append(cost1 + cost2)
    print(min(counters))


### FIXED CODE ###

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

w_counter_all = 0
for i in range(n):
    if s[i] == '.': # white
        w_counter_all += 1

if s[0] == '.':
    cost1 = 0
else:
    cost1 = 1
cost1_list = [cost1]
for i in range(1, n):
    if s[i] == '#':
        # black
        cost1 += 1
    cost1_list.append(cost1)


cost_all = [w_counter_all]
for i in range(n):
    cost_all.append(n - i - 1 - cost1_list[-1] + cost1_list[i] * 2)
print(min(cost_all))
### BUGGY CODE ###

from collections import *
import itertools
import sys
sys.setrecursionlimit(10**5)
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()

X = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
p = [x for x, _ in X]
sc = [x for _, x in X]

DP = {}
def opt(l, i):
    r = N - i + l - 1
    if i == N: return 0
    T = l, i
    if T in DP:
        return DP[T]
    v1 = abs(p[i]- l)*sc[i] + opt(l+1, i+1)
    v2 = abs(p[i] - r)*sc[i] + opt(l, i+1)
    DP[T] = max(v1, v2)
    return DP[T]

print(opt(0, 0))


### FIXED CODE ###

from collections import *
import itertools
import sys
sys.setrecursionlimit(10**5)
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()

X = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
p = [x for x, _ in X]
sc = [x for _, x in X]

DP = [[-1]*N for _ in range(N)]
def opt(l, i):
    r = N - i + l - 1
    if i == N: return 0
    if DP[i][l] != -1: return DP[i][l]
    v1 = abs(p[i]- l)*sc[i] + opt(l+1, i+1)
    v2 = abs(p[i] - r)*sc[i] + opt(l, i+1)
    DP[i][l] = max(v1, v2)
    return DP[i][l]

print(opt(0, 0))
### BUGGY CODE ###


n = int(input())
s = int(input())
rtn = int(n**0.5)+1

def f(b,n):
    if n<b:
        return n
    return f(b,n//b) + n % b

if n < s or (n // 2)+1 < s < n :
    print("-1")
elif s == n:
    print(n+1)
elif s == n//2 +1:
    if n % 2 == 1:
        print(n//2 + 1)
    else:
        print("-1")
elif (n//3) + 2 < s <= n//2:
    print(n-s+1)
elif s == 1:
    def check(n,b):
        if n == 1:
            return b
        else:
            if n % b !=0 :
                return 0
            else:
                return check(n // b,b)
    for b in range(2,rtn):
        r = check(n,b)
        if r:
            print(r)
            exit()
    print(n)
else:
    x = n // s
    if s - (n //(x+1))  <= x:
        x = x + 1
    if 5 < n/(x -1) - n/x :
        for b in range(n//x, n//(x-1)):
            if f(b,n) == s:
                print(b)
                exit()
        for i in range(x-1,2,-1):
            for b in range(n//i + (n//x)//(n//i), n//i + (n//x)//(n//i)  + (2*n//x - n//(x+1))//(x-i)):
                if f(b,n) == s:
                    print(b)
                    exit()
    else:
        for b in range(2,(n//3)+3):
            if f(b,n) == s:
                print(b)
                exit()
    print(n-s+1)


### FIXED CODE ###

n = int(input())
s = int(input())
rtn = -1* int( -1 * (n**0.5))
def f(b,n):
    if n<b:
        return n
    return f(b,n//b) + n % b
if n < s or (n // 2)+1 < s < n :
    print("-1")
elif s == n:
    print(n+1)
elif s == n//2 +1:
    if n % 2 == 1:
        print(n//2 + 1)
    else:
        print("-1")
elif (n//3) + 2 < s <= n//2:
    print(n-s+1)
else:
    for b in range(2,rtn+1):
        if f(b,n) == s:
            print(b)
            exit()
    for p in range(rtn,0,-1):
        if (n-s) % p == 0:
            b = (n-s)//p + 1
            if f(b,n) == s:
                print(b)
                exit()
    print(n-s+1)