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

# dp[i][j]=(i番目まで使って最後の高さがjであるようなものの美しさの最大値)
# dp[i][j]=max(dp[i-1][k])+a[i](h[i]==j,0<=k<j),dp[i-1][j](otherwise)

def segfunc(x,y):
    return max(x,y)


def init(init_val):
    #set_val
    for i in range(n):
        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


N=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
n=N+1
#####単位元######
ide_ele = 0 #変える
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
dp=[0]*n
init(dp)
for i in range(N):
    # dp[h[i]]の値をdp[k](kは[0,h[i]))の最大値+a[i]にする
    # 手で書いてみると動きがわかりやすい
    update(h[i],query(0,h[i])+a[i])
print(query(0,n))

### FIXED CODE ###

# dp[i][j]=(i番目まで使って最後の高さがjであるようなものの美しさの最大値)
# dp[i][j]=max(dp[i-1][k])+a[i](h[i]==j,0<=k<j),dp[i-1][j](otherwise)

def segfunc(x,y):
    return max(x,y)


def init(init_val):
    #set_val
    for i in range(n):
        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


N=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
n=N+1
#####単位元######
ide_ele = 0 #変える
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
dp=[0]*n
init(dp)
for i in range(N):
    update(h[i],query(0,h[i])+a[i])
print(query(0,n))
### BUGGY CODE ###

N = int(input())
S = list(input())
cs = set(S)

from itertools import product
pro = product(cs, repeat=3)

ans = 0
for c in pro:
    tmp = 0
    for i in range(N):
        if c[tmp] == S[i]: tmp += 1
        if tmp == 3:
            ans += 1
            break
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
sS = set(S)
from itertools import product
sS = product(sS,repeat=3)
c = 0

for i in sS:
	if i[0] in S:
		a = S.index(i[0])
		if i[1] in S[a+1:]:
			b = S[a+1:].index(i[1]) + a + 1
			if i[2] in S[b+1:]:
				c += 1
print(c)
### BUGGY CODE ###

class SegmentTree:
    def __init__(self, a):
        self.padding = -float('inf')    
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = max(self.seg_data[i], self.seg_data[i-1])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = max(self.seg_data[2*idx+1], self.seg_data[2*idx+2])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = max(result, self.seg_data[idx1])
                if idx2&1 == 1: # idx2が奇数
                    result = max(result, self.seg_data[idx2])
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result


N, K = map(int, input().split())
A = 300001
st = SegmentTree([0]*A)

for i in range(N):
    a = int(input())
    l = max(0, a-K)
    r = min(A-1, a+K)
    max_len = st.query(l, r+1)
    st.update(a, max_len+1)

print(st.query(1, A))

### FIXED CODE ###

class SegmentTree:
    def __init__(self, a):
        self.padding = -float('inf')    
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = max(self.seg_data[i], self.seg_data[i-1])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = max(self.seg_data[2*idx+1], self.seg_data[2*idx+2])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = max(result, self.seg_data[idx1])
                if idx2&1 == 1: # idx2が奇数
                    result = max(result, self.seg_data[idx2])
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result


N, K = map(int, input().split())
A = 300001
st = SegmentTree([0]*A)

for i in range(N):
    a = int(input())
    l = max(0, a-K)
    r = min(A-1, a+K)
    max_len = st.query(l, r+1)
    st.update(a, max_len+1)

print(st.query(1, A))
### BUGGY CODE ###

m = 'Male'
f = 'Female'
v = 'Vacant'

N = int(input())
x = 0
y = N - 1
cnt = 2
print(x)
h_bef = input()
if h_bef == v:
	print(0)
	exit()
while cnt < 20:
	p = (x+y+1)//2
	print(p, cnt)
	h = input()
	if h == v:
		break
	mod = 0 if h_bef == h else 1
	if (p-x) % 2 == mod:
		x = p
	else:
		y = p - 1
	h_bef = h
	cnt += 1
exit()

### FIXED CODE ###

m = 'Male'
f = 'Female'
v = 'Vacant'

N = int(input())
x = 0
y = N
cnt = 1
print(0)
p_bef = 0
h_bef = input()
if h_bef == v:
	exit()
while cnt < 50:
	p = (x+y+1)//2
	print(p)
	h = input()
	if h == v:
		break
	mod = 0 if h_bef == h else 1
	if (p-x) % 2 == mod:
		x = p
		h_bef = h
	else:
		y = p
	cnt += 1
exit()
### BUGGY CODE ###

s = input()
n = len(s)
result = [0 for _ in range(n)]
for i in range(n):
  p = i
  if s[p] == 'R':
    p += 1
    prev = 'R'
  else:
    p -= 1
    prev = 'L'
  count = 1
  while True:
    if s[p] == 'R':
      p += 1
      prev = 'R'
    else:
      if prev == 'R':
        if count % 2 == 0:
          result[p] += 1
        else:
          result[p - 1] += 1
        break
      p -= 1
      prev = 'L'
    count += 1
print(' '.join(map(str, result)))

### FIXED CODE ###

s = input()
n = len(s)
result = [0 for _ in range(n)]
start = 0
c = 'R'
for i in range(1, n):
  if s[i] != c:
    if c == 'R':
      result[i - 1] += (i - start) // 2 + (i - start) % 2
      result[i] += (i - start) // 2
      c = 'L'
    else:
      result[start] += (i - start) // 2 + (i - start) % 2
      result[start - 1] += (i - start) // 2
      c = 'R'
    start = i
result[start] += (n - start) // 2 + (n - start) % 2
result[start - 1] += (n - start) // 2
print(*result)
### BUGGY CODE ###

n = int(input())
st = {}

maxi = 0

for _ in range(n):
    s = input()

    if s in st:
        st[s] += 1
    else:
        st[s] = 1

    if st[s] > maxi:
        maxi = st[s]

max_k = sorted([kv[0] for kv in st.items() if kv[1] == max(st.values())])

for k in max_k:
    print(k)

### FIXED CODE ###

n = int(input())
st = {}

maxi = 0

for _ in range(n):
    s = input()

    if s in st:
        st[s] += 1
    else:
        st[s] = 1

    if st[s] > maxi:
        maxi = st[s]

ans = []
for k, v in st.items():
    if v==maxi:
        ans.append(k)

ans = sorted(ans)
for a in ans:
    print(a)
### BUGGY CODE ###

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

ans = 0
for X in range(1, 10 ** 5 + 2):
  cnt = 0
  for i in range(N):
    if X - 1 <= A[i] <= X + 1:
      cnt += 1
  ans = max(ans, cnt)
  
print(ans)

### FIXED CODE ###

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

count = [0] * (10 ** 5 + 1)

for a in A:
  count[a] += 1
  
ans = 0  
for i in range(1, 10 ** 5):
  X = count[i-1] + count[i] + count[i+1]
  ans = max(ans, X)
  
print(ans)
### BUGGY CODE ###

def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    a, b = list(map(int, input().rstrip('\n').split()))
    gcd = fractions.gcd(a, b)
    cnt = 1

    while True:
        if gcd == 1:
            break
        else:
            for i in range(2, gcd + 1):
                if gcd % i == 0:
                    cnt += 1
                    while True:
                        if gcd % i == 0:
                            gcd //= i
                        else:
                            break
    print(cnt)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    import fractions
    input = sys.stdin.readline
    a, b = list(map(int, input().rstrip('\n').split()))
    gcd = fractions.gcd(a, b)
    cnt = 1
    for i in range(2, int(gcd ** 0.5) + 1):
        if gcd % i == 0:
            cnt += 1
            while True:
                if gcd % i == 0:
                    gcd //= i
                else:
                    break
    if gcd != 1:
        cnt += 1
    print(cnt)


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

import sys

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

def beki(n):
    ans = 1
    for _ in range(int(n)):
        ans = (ans * 2) % (10 ** 9 + 7)
    return int(ans)

if n % 2 == 0:
    i = 1
    while True:
        if i in a:
            a.remove(i)
        else:
            print(0)
            sys.exit()
        if i in a:
            a.remove(i)
        else:
            print(0)
            sys.exit()
        i += 2
        if a == []:
            break       
    print(beki(n / 2))

elif n == 1:
    if a == [0]:
        print("1")
    else:
        print("0")
else:
    i = 2
    while True:
        if i in a:
            a.remove(i)
        else:
            print(0)
            sys.exit()
        if i in a:
            a.remove(i)
        else:
            print(0)
            sys.exit()
        i += 2
        if a == [0]:
            break
    print(beki((n - 1) / 2))

### FIXED CODE ###

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

def beki(n):
    ans = 1
    for _ in range(int(n)):
        ans = (ans * 2) % (10 ** 9 + 7)
    return int(ans)

if n % 2 == 0:
    hikaku = []
    for i in range(1, n, 2):
        hikaku += [i, i]
    if sorted(a) == hikaku:
        print(beki(n / 2))
    else:
        print(0)

elif n == 1:
    if a == [0]:
        print(1)
    else:
        print(0)
else:
    hikaku = [0]
    for i in range(2, n, 2):
        hikaku += [i, i]
    if sorted(a) == hikaku:
        print(beki((n - 1) / 2))
    else:
        print(0)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0

for i in range(N-2):
    si = S[i]
    

    for j in range(i+1,N-1):
        sj = S[j]
        if si==sj:
            continue
        else:
            RGB = set(['R','G','B'])
            RGB -= set([si,sj])
            k=j+1
            kji=j-i
            count += (S[k : k + kji-1]+S[k+kji:]).count(*RGB)
print(count)

### FIXED CODE ###

N = int(input())
S = input()
count = 0

RGBlist = [[S.count('R')],[S.count('G')],[S.count('B')]]


for i in range(1,N):
    RGBlist[0].append(RGBlist[0][-1] - (S[i-1] == 'R'))
    RGBlist[1].append(RGBlist[1][-1] - (S[i-1] == 'G'))
    RGBlist[2].append(RGBlist[2][-1] - (S[i-1] == 'B'))

for i in range(N-2):
    si = S[i]
    
    for j in range(i+1,N-1):
        sj = S[j]
        if si==sj:
            continue
        else:
            RGB = set(['R','G','B'])
            RGB -= set([si,sj])
            k=j+1
            kji=j-i
            if RGB == {'R'}:
                rgb = 0
            elif RGB =={'G'}:
                rgb = 1
            else:
                rgb = 2
            if k+kji-1 < len(S):
                count += RGBlist[rgb][k] - ({S[k+kji-1]} == RGB)
            else:
                count += RGBlist[rgb][k]
            
print(count)
### BUGGY CODE ###

N = int(input())
import itertools
from collections import deque
ans = deque()
l = []
r = deque()
for i in range(N):
  l.append(chr(97+i))
  r.append(l.copy())
  
p = [[] for _ in range(N)]
p[0].append('a')
for i in range(1,N):
  for j in r[i]:
    for k in p[i-1]:
      p[i].append(k+j)
      
p = p[-1]
for i in p:
  a = [0]*10
  for j in i:
    x = ord(j)-97
    a[x]=1
    if x==0:
      judge = True
      continue
    elif a[x-1]==1:
      judge = True
      continue
    else:
      judge = False
      break
  if judge:
    ans.append(i)
ans = set(ans)
ans = sorted(list(ans))
for a in ans:
  print(a)

### FIXED CODE ###

N = int(input())
from collections import deque
import itertools
ans = deque()
l = []
r = deque()
for i in range(N):
  l.append(chr(97+i))
  r.append(l.copy())
  

p = [[[] for _ in range(N)] for _ in range(N)]
p[0][0].append('a')
for i in range(1,N):
  for j in r[i]:
    x = ord(j)-97
    for n,k in enumerate(p[i-1][max(0,x-1):],max(0,x-1)):
      for m in k:
        p[i][max(n,x)].append(m+j)


p = p[-1]
p = list(itertools.chain.from_iterable(p))
p = sorted(p)
for q in p:
  print(q)
### BUGGY CODE ###

N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split(" "))) for i in range(N)]

class Cycle(Exception):
    pass

paths = {}
st = set()

def dfs(a, b):

    node = (min(a, b), max(a, b))

    if node in paths:
        return paths[node]

    if node in st:
        raise Cycle()

    st.add(node)

    ns = [1]
    i = A[a].index(b)
    for j in range(i):
        ns.append(1 + dfs(a, A[a][j]))

    i = A[b].index(a)
    for j in range(i):
        ns.append(1 + dfs(b, A[b][j]))

    st.remove(node)
    paths[node] = max(ns)
    return paths[node]

ans = -1
try:
    for i in range(N):
        ans = max(ans, dfs(i, A[i][-1]))
    print(ans)
except Cycle:
    print(-1)


### FIXED CODE ###

import sys

N = int(input())
A = [list(map(lambda x: int(x) - 1, input().split(" "))) for i in range(N)]

canUse = set(range(N))

ans = 0
done = 0
while done < N:
    ans += 1
    canUseNew = set()
    # print("LC", len(canUse))
    for n in canUse:
        if not A[n]:
            continue

        first = A[n][-1]
        if first in canUseNew or n in canUseNew:
            continue

        if A[first][-1] == n:
            # print("Do", n + 1, first + 1)
            A[n].pop()
            if len(A[n]) == 0:
                done += 1
            A[first].pop()
            if len(A[first]) == 0:
                done += 1
            canUseNew.add(n)
            canUseNew.add(first)

    if len(canUseNew) == 0:
        print(-1)
        sys.exit(0)
    canUse = canUseNew

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

#ABC072-C
import collections
import itertools

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

cnt = 0

for i in a:
    tmp = a.count(i-1) + a.count(i) + a.count(i+1)
    if tmp > cnt:
        cnt = tmp
        
print(cnt)


### FIXED CODE ###

#ABC072-C
n = int(input())
a = list(map(int,input().split()))
 
cnt = [0] * 100002


for i in a:
    cnt[i] += 1
    cnt[i+1] += 1
    cnt[i+2] += 1
    
    

    
        
print(max(cnt))
### BUGGY CODE ###

_, q = map(int, input().split())
s = input()

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

### FIXED CODE ###

n, q = map(int, input().split())
s = input()

t = [0] * (n)
for i in range(n-1):
    if s[i:i+2] == 'AC':
        t[i+1] = t[i]+1
    else:
        t[i+1] = t[i]

for _ in range(q):
    l, r = map(int, input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

N = int(input())

list = []
for i in range(0, N):
    x, y, h = [int(x) for x in input().split()]
    list.append((x, y, h))

'''
def calcCenterHeight(X, Y, Cx, Cy, Ch):
    return Ch + abs(X - Cx) + abs(Y - Cy)
'''


def calcCenterHeight(X, Y, Cx, Cy, Ch):
    s = set()
    H = Ch + abs(X - Cx) + abs(Y - Cy)
    s.add(H)
    if Ch == 0:
        for h in range(0, H):
            s.add(h)
    return s


from functools import reduce

for X in range(0, 101):
    for Y in range(0, 101):
        s = [calcCenterHeight(X, Y, Cx, Cy, Ch) for Cx, Cy, Ch in list]
        a = reduce(lambda a, b: a & b, s)
        # print(X, Y, s, a)
        if len(a) == 1:
            print(X, Y, a.pop())


### FIXED CODE ###

import sys

N = int(input())

list = []
for i in range(0, N):
    x, y, h = [int(x) for x in input().split()]
    list.append((x, y, h))
    # if (h != 0):
    # list.append((x, y, h))

for X in range(0, 101):
    for Y in range(0, 101):
        b = True
        H = 0
        for Cx, Cy, Ch in list:
            if Ch != 0:
                H = Ch + abs(X - Cx) + abs(Y - Cy)
        for Cx, Cy, Ch in list:
            h = max(H - abs(X - Cx) - abs(Y - Cy), 0)
            if Ch != h:
                b = False
        if b == True:
            print(X, Y, H)
            sys.exit(0)
### BUGGY CODE ###

k = int(input())
if  k%2==0 or k%5==0:
    print(-1)
else:
    K = int(str(k)[-1])
    # print(K)
    if K==1:
        # print("a")
        x = 7
    elif K==3:
        x=9
    elif K==7:
        x = 1
    elif K==9:
        x = 3
    z = 0
    # print(x)
    while True:
        s = 10*z + x
        q = k * s
        if str(q)=="7"*len(str(q)):
            print(len(str(q)))
            break
        z+=1


### FIXED CODE ###

k = int(input())
c = 0
if k%2 ==0 or k%5==0:
    print(-1)
    c=1
elif k==1:
    print(1)
    c=1
if c==0:
    t = 7

    for i in range(k):
        if int(t)%k==0 :
            print(i+1)
            break
        t = (10*t+7)%k
### BUGGY CODE ###

import sys
import numpy as np
readline = sys.stdin.readline

MOD = 10 ** 9 + 7


def main():
    def fact_table(N, MOD):
        inv = np.empty(N, np.int64)
        inv[0] = 0
        inv[1] = 1
        for n in range(2, N):
            q, r = divmod(MOD, n)
            inv[n] = inv[r] * (-q) % MOD
        fact = np.empty(N, np.int64)
        fact[0] = 1
        for n in range(1, N):
            fact[n] = n * fact[n - 1] % MOD
        fact_inv = np.empty(N, np.int64)
        fact_inv[0] = 1
        for n in range(1, N):
            fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD
        return fact, fact_inv, inv

    fac, finv, inv = fact_table(2_000_010, MOD)
    K = int(readline())
    N = len(readline())
    f = np.zeros(K + 1, np.int64)
    f = fac[N - 1:K + N] * finv[N - 1] % MOD * finv[:K + 1] % MOD

    x = 1
    for i in range(1, K + 1):
        x = (x * 25) % MOD
        f[i] = f[i] * x % MOD
    for i in range(1, K + 1):
        f[i] += f[i - 1] * 26
        f[i] %= MOD

    print(f[-1])


import numba
from numba.pycc import CC
i8 = numba.from_dtype(np.int64)
signature = (i8, i8, i8)

main()


### FIXED CODE ###

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

def main(K, N, MOD):
    def fact_table(N, MOD):
        inv = np.empty(N, np.int64)
        inv[0] = 0
        inv[1] = 1
        for n in range(2, N):
            q, r = divmod(MOD, n)
            inv[n] = inv[r] * (-q) % MOD
        fact = np.empty(N, np.int64)
        fact[0] = 1
        for n in range(1, N):
            fact[n] = n * fact[n - 1] % MOD
        fact_inv = np.empty(N, np.int64)
        fact_inv[0] = 1
        for n in range(1, N):
            fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD
        return fact, fact_inv, inv

    fact, fact_inv, inv = fact_table(2_000_010, MOD)
    f = np.zeros(K + 1, np.int64)
    f = fact[N - 1:K + N] * fact_inv[N - 1] % MOD * fact_inv[0:K + 1] % MOD

    x = 1
    for i in range(1, K + 1):
        x = (x * 25) % MOD
        f[i] = f[i] * x % MOD
    for i in range(1, K + 1):
        f[i] += f[i - 1] * 26
        f[i] %= MOD
    return f[-1]

if sys.argv[-1] == 'ONLINE_JUDGE':  #　なにそれ
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8)

    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()


from my_module import main
K = int(readline())
N = len(read().rstrip())

print(main(K, N, MOD))
### BUGGY CODE ###

import math                                                       
A, B, N = map(int, input().split())

# A, B, N = 11, 10, 9

maxR = -1
maxX = 0
for x in range(0, N+1):
    R = math.floor(A*x/B) - A * math.floor(x/B)
    if R >= maxR:
        maxR = R
        maxX = x
print (maxR)

### FIXED CODE ###

import math                                                       
A, B, N = map(int, input().split())

# A, B, N = 11, 10, 9
T = N//B
maxR = -1
maxT = 0
# for x in range(1, T+2):
    # t = min(x*B-1,N)
    # R = math.floor(A*t/B) - A * math.floor(t/B)
    # if R >= maxR:
    #     maxR = R
    #     maxT = t
t = min(B-1,N)
maxR = math.floor(A*t/B) - A * math.floor(t/B)
print (maxR)
### BUGGY CODE ###

import fractions
import functools

N = int(input())
A = [int(i) for i in input().split()]

answer = 0
for i in range(N):
  tmp = A[:]
  tmp.pop(i)
  m = functools.reduce(fractions.gcd, tmp)
  if answer < m:
    answer = m
print(answer)

### FIXED CODE ###

import fractions as math

n = int(input()) # 入力データの個数
a = list(map(int, input().split())) # 入力データ
 
l = [a[0] for _ in range(n+2)] # データの左端を初期値として追加
r = [a[-1] for _ in range(n+2)] # データの右端を初期値として追加
 
for i in range(n): # データのどこを置き換えるか
    l[i+1] = math.gcd(l[i], a[i]) # 置きかえる部分より左の最大公約数と置きかえる部分の最大公約数を更新する
    r[-(i+2)] = math.gcd(r[-(i+1)], a[-(i+1)]) # 置きかえる部分より右の最大公約数と置きかえる+1の最大公約数を更新する 
l[0] = r[0] = l[-1] = r[-1] = 0 # 初期値形に0を入れていく
 
ans = [math.gcd(l[i], r[i+2]) for i in range(n)] # 最大公約数のセットを改めて配列へ
print(max(ans)) # 最大公約数を出力
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K + 1):
    for y in range(K + 1):
        for z in range(K + 1):
            if S == x + y + z:
                count += 1
print(count)

### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K + 1):
    for y in range(K + 1):
        z = S - (x + y)
        if 0 <= z <= K:
            count += 1
print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
index = 0
ans = 0
for i in range(N-K+1):
    if sum(p[index:index+K]) < sum(p[i:i+K]):
        index = i
for i in range(index, index+K):
    ans += 0.5*p[i]*(p[i]+1)/p[i]
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
dp = [0]*N
dp[0] = sum(p[:K])
for i in range(N-K):
    dp[i+1] = dp[i] - p[i] + p[i+K]
index = dp.index(max(dp))
for i in range(index, index+K):
    ans += 0.5*p[i]*(p[i]+1)/p[i]
print(ans)
### BUGGY CODE ###

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

l = []
for i in range(1, n + 1):
    l.append(a.index(i) + 1)
    
print(*l)

### FIXED CODE ###

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

l = sorted(range(len(a)), key=a.__getitem__)
for i in l:
    print(i + 1, end = " ")