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

# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def dfs(graph, start, ans, n):
    queue = deque([])
    queue.append(start)
    visited = [False] * n
    visited[start] = True

    while queue:
        parent = queue.pop()
        for child in graph[parent].keys():
            if visited[child]:
                continue
            ans[child] += ans[parent]
            queue.append(child)
    
    print(' '.join(map(str, ans)))

n,q = map(int, input().split())
tree = {}
start = 0
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

ans = [0]*n
for _ in range(q):
    p, x = map(int,input().split())
    p -= 1
    ans[p] += x
dfs(tree, start, ans, n)


### FIXED CODE ###

# https://atcoder.jp/contests/abc138/tasks/abc138_d

from collections import deque

def bfs(graph, start, query, n):
    queue = deque([])
    acc = query[start] if start in query else 0
    queue.append([start, acc])
    ans = [-1] * n
    ans[start] = acc

    while queue:
        idx, acc = queue.popleft()
        for child in graph[idx].keys():
            if ans[child] >= 0:
                continue
            ans[child] = acc
            if child in query:
                ans[child] += query[child]
            queue.append([child, ans[child]])
    
    print(' '.join(map(str, ans)))

n,q = map(int, input().split())
tree = {}
start = 0
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if a not in tree:
        tree[a] = {}
    tree[a][b] = 1
    if b not in tree:
        tree[b] = {}
    tree[b][a] = 1

query = {}
for _ in range(q):
    p, x = map(int,input().split())
    p -= 1
    if p not in query:
        query[p] = x
    else:
        query[p] += x
bfs(tree, start, query, n)
### BUGGY CODE ###

n = input()
p = input().split()

i_cnt = 1
current_max = {'idx': 0, 'value': 0}

for j in range(len(p)):
  for i in range(current_max['idx'], j):
    if current_max['value'] <= int(p[i]): 
      current_max['idx'] = i
      current_max['value'] = int(p[i])
    if int(p[i]) < int(p[j]):
      break
    if j-1 == i:
      i_cnt += 1

print(i_cnt)

### FIXED CODE ###

n = input()
p = input().split()

i_cnt = 1
current_max = {'idx': 0, 'value': 0}

for j in range(len(p)):
  for i in range(current_max['idx'], j):
    current_max['idx'] = i
    if current_max['value'] <= int(p[i]): 
      current_max['value'] = int(p[i])
    if int(p[i]) < int(p[j]):
      break
    if j-1 == i:
      i_cnt += 1

print(i_cnt)
### BUGGY CODE ###

import itertools


N = int(input())
S = input()

ptn = [i for i in range(N)]

ans = []
for i in range(1, N+1):
    c = list(itertools.combinations(ptn, i))
    for v in c:
        tmp = ''
        for _ in v:
            tmp += S[_]
        ans.append(tmp)

cnt = 0

for _ in (ans):
    if (len(_) == len(set(_))):
        cnt += 1

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


### FIXED CODE ###

N = int(input())
S = input()

M = 10**9 + 7
cnt = [0] * 26

for i in range(N):
    cnt[ord(S[i]) - ord('a')] += 1

ans = 1
for i in range(26):
    ans *= (cnt[i] + 1)
    ans %= M

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

import sys
from collections import Counter 

N,*a = map(int,open(0).read().split())
for i in range(1<<N):
    bit_str = format(i,'b').zfill(N)
    r_bit_str = list(reversed(bit_str))
    flg = True
    for j in range(N):
        parts_bit = r_bit_str[j::j+1]
        c = Counter(parts_bit)
        sum1 = c["1"]
        if sum1 % 2 != a[j]:
            flg = False
            break
    if flg:
        ans = []
        for i in range(len(r_bit_str)):
            if r_bit_str[i] == "1":
                ans.append(str(i+1))
        print(len(ans))
        print(" ".join(ans))
        sys.exit()
print(-1)  
    

### FIXED CODE ###

from collections import Counter

N,*a = map(int,open(0).read().split())
ans = []
for i in range(N)[::-1]:
    part_rem = sum(a[i::i+1]) % 2
    if a[i] == 0:
        if part_rem == 1:
            a[i] = abs(a[i] - 1) 
    elif a[i] == 1:
        if part_rem == 0:
            a[i] = abs(a[i] - 1)
            
c = Counter(a)            
print(c[1])
for i in range(N):
    if a[i] == 1:
        print(i+1,end=" ")
print()
### BUGGY CODE ###



if __name__ == '__main__':
    s = input()
    q = int(input())
    ans = s
    rev_count = 0
    alist =[]
    anslist = []

    for i in range(q):
        a = [i for i in input().split()]
        alist.append(a)
        if len(a) == 1:
            rev_count = rev_count +1

    if rev_count % 2 ==1:
        ans = ans[::-1]
    anslist.append(ans)


    for i in alist:
        if len(i) == 1:
            rev_count = rev_count -1
        else:
            if int(i[1]) == 1:
                if rev_count % 2 == 1:
                    anslist.append(i[2])
                else:
                    anslist.insert(0,i[2])

            else:
                if rev_count % 2 == 1:
                    anslist.insert(0,i[2])
                else:
                    anslist.append(i[2])

    print("".join(anslist))


### FIXED CODE ###

from collections import deque

if __name__ == '__main__':
    s = input()
    q = int(input())
    ans = s
    rev_count = 0
    leftList = deque()
    rightList =[]
    alist =[]

    for i in range(q):
        a = [i for i in input().split()]
        alist.append(a)
        if len(a) == 1:
            rev_count = rev_count +1

    if rev_count % 2 ==1:
        ans = ans[::-1]

    for i in alist:
        if len(i) == 1:
            rev_count = rev_count -1
        else:
            if int(i[1]) == 1:
                if rev_count % 2 == 1:
                    rightList.append(i[2])
                else:
                    leftList.appendleft(i[2])

            else:
                if rev_count % 2 == 1:
                    leftList.appendleft(i[2])
                else:
                    rightList.append(i[2])

    ans = ''.join(leftList)+ ans+''.join(rightList)

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

import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

ans = set()


def f(i, j):
    seen[i][j] = 1
    if S[i][j] == '.':
        ans.add((s, (i, j)))
    if i != 0:
        if seen[i-1][j] == 0 and S[i-1][j] != S[i][j]:
            f(i-1, j)
    if i != H-1:
        if seen[i+1][j] == 0 and S[i+1][j] != S[i][j]:
            f(i+1, j)
    if j != 0:
        if seen[i][j-1] == 0 and S[i][j-1] != S[i][j]:
            f(i, j-1)
    if j != W-1:
        if seen[i][j+1] == 0 and S[i][j+1] != S[i][j]:
            f(i, j+1)


for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            seen = [[0] * W for i in range(H)]
            s = (i, j)
            f(i, j)

print(len(ans))


### FIXED CODE ###

import collections
import sys
sys.setrecursionlimit(1000000)


H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]


seen = [[False] * W for i in range(H)]
move = ((-1, 0), (1, 0), (0, -1), (0, 1))

q = collections.deque()


def bfs(i, j):
    b, w = 0, 0
    seen[i][j] = True
    q.append((i, j))

    while q:
        ci, cj = q.popleft()

        if S[ci][cj] == '#':
            b += 1
        else:
            w += 1

        for di, dj in move:
            ni = ci+di
            nj = cj+dj
            if 0 <= ni < H and 0 <= nj < W:
                if seen[ni][nj] is False and S[ci][cj] != S[ni][nj]:
                    seen[ni][nj] = True
                    q.append((ni, nj))

    return b*w


ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#' and seen[i][j] is False:
            ans += bfs(i, j)

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

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

if n % 2 == 0:
    for i in range(n//2):
        ans *= a[i]
        ans *= a[n-i-1]
elif n % 2 == 1:
    for i in range(n//2):
        ans *= a[i]
        ans *= a[n-i-1]
    ans *= a[n//2+1]

if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
a.sort()
if a[0] == 0:
    ans = 0
    print(ans)
    exit()

for i in range(n):
    ans *= a[i]
    if ans > 10**18:
        print(-1)
        exit()

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

n, k = map(int, input().split())
H = list(map(int, input().split()))
INF = 10**10
C = [INF]*n
C[0] = 0
for i in range(1, n):
  min_j = max(i-k, 0)
  for j in range(i-1, min_j-1, -1):
    C[i] = min(C[i], C[j]+abs(H[i]-H[j]))
print(C[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
H = list(map(int, input().split()))
INF = 10**10
C = [INF]*n
C[0] = 0
for i in range(1, n):
  min_j = max(i-k, 0)
  for j in range(i-1, min_j-1, -1):
    C[i] = min(C[i], C[j]+abs(H[i]-H[j]))
print(C[n-1])
### BUGGY CODE ###

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

Frends = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a < b:
        Frends[a].append(b)
    else:
        Frends[b].append(a)

Blocked = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    if c < d:
        Blocked[c].append(d)
    else:
        Blocked[d].append(c)

# process
# 友人グループを作成
fg = []
for i in range (N):
    fs = Frends[i]
    for f in fs:
        t = -1

        j = 0
        fglen = len(fg)
        while j < fglen:
            g = fg[j]
            if i in g and f in g:
                if t < 0:
                    t = j              
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    fglen -= 1
            elif not (i in g or f in g):
                j += 1
                continue
            else:
                if t < 0:
                    if i in g:
                        g.add(f)
                    else:
                        g.add(i)

                    t = j
                else:
                    fg[t] = fg[t] | g
                    fg.pop(j)
                    fglen -= 1
            j += 1
            
        if t < 0:
            fg.append(set([i, f]))

# 友人候補を抽出
cand = []
for i in range(N):
    for g in fg:
        if i in g:
            for f in g:
                if i < f and not f in Frends[i] and not f in Blocked[i]:
                    cand.append((i, f,))

# 友人候補をカウント
ans = [0 for _ in range(N)]
for c in cand:
    a, b = c
    ans[a] += 1
    ans[b] += 1

# output
#print(fg)
#print(cand)
print(" ".join(map(str, ans)))


### FIXED CODE ###

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

Friends = [set() for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    Friends[a].add(b)
    Friends[b].add(a)

Blocked = [set() for _ in range(N)]
for _ in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Blocked[c].add(d)
    Blocked[d].add(c)

# process
# 友人グループを作成
checked = set()
ans = [0]*N

for i in range (N):
    if i in checked:
        continue
    
    fg = set()

    stack = list(Friends[i])
    while stack:
        f = stack.pop()
        if f in checked:
            continue

        checked.add(f)
        fg.add(f)
        stack.extend(Friends[f])

    for f in fg:
        ans[f] += len(fg)-1-len(fg&(Friends[f]|Blocked[f]))

# output
print(" ".join(map(str, ans)))
### BUGGY CODE ###

from fractions import gcd
K = int(input())
sum = 0
for a in range(1, K+1):
  for b in range(a+1, K+1):
    for c in range(b+1, K+1):
      sum += gcd(gcd(a, b), c)
sum *= 6
for j in range(1, K+1):
  for k in range(j+1, K+1):
    sum += gcd(j, k)*6
for l in range(1, K+1):
  sum += l 
print(sum)

### FIXED CODE ###

from math import gcd
K = int(input())
sum = 0
for a in range(1, K+1):
  for b in range(a+1, K+1):
    for c in range(b+1, K+1):
      sum += gcd(gcd(a, b), c)
sum *= 6
for j in range(1, K+1):
  for k in range(j+1, K+1):
    sum += gcd(j, k)*6
for l in range(1, K+1):
  sum += l 
print(sum)
### BUGGY CODE ###

import collections

def main():
    S = input()
    result = 0
    t = [0] * (len(S) + 1)
    for i in range(len(S)):
        t[i+1] = int(S[-i-1:]) % 2019
    count_dict = collections.Counter(t)
    for a, b in count_dict.items():
        result += b*(b-1) // 2

    print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    S = list(input())
    N = len(S)
    t = 0
    A = [0] * 2019
    A[0] += 1
    d = 1
    for s in reversed(S):
        d *= 10
        d %= 2019
        t += (int(s) * d)
        t %= 2019
        A[t] += 1
    result = sum([a*(a-1)//2 for a in A])
    print(result)


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

def solve(N, Q, S, L_R):
    answers = [None] * Q
    q = 0
    for l, r in L_R:
        pstr = S[l - 1:r]
        count = 0
        for i in range(len(pstr) - 1):
            if pstr[i:i + 2] == "AC":
                count += 1
        answers[q] = count
        q += 1
    return answers


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
for ans in solve(N, Q, S, L_R):
    print(ans)

### FIXED CODE ###

def solve(N, Q, S, L_R):
    memo = [None] * N
    cumsum = 0
    for i in range(len(S) - 1):
        memo[i] = cumsum
        if S[i] == "A" and S[i + 1] == "C":
            cumsum += 1
    memo[N - 1] = cumsum
    for l, r in L_R:
        print(memo[r - 1] - memo[l - 1])


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
solve(N, Q, S, L_R)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000)

D, goal = map(int, input().split())
q_num, bonus = [], []
for i in range(1,D+1):
  q, b = map(int, input().split())
  q_num.append(q)
  bonus.append(b)
ans = 100000

def rec(comb, next_n, current_score):
  if next_n == D + 1:
    global ans
    if current_score >= goal:
      ans = min(ans, sum(comb))
  else:
    for i in range(q_num[next_n-1]):
      rec(comb + [i], next_n+1, current_score + i * next_n * 100)
    rec(comb + [q_num[next_n-1]], next_n+1, current_score + q_num[next_n-1] * next_n * 100 + bonus[next_n-1])
rec([], 1, 0)

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000)

D, goal = map(int, input().split())
q_num, bonus = [], []
for i in range(1,D+1):
  q, b = map(int, input().split())
  q_num.append(q)
  bonus.append(b)
ans = 100000

def rec2(current_qn, next_n, current_score, tyuuto_done):
  if next_n == D + 1:
    global ans
    if current_score >= goal:
      ans = min(ans, current_qn)
  else:
    rec2(current_qn+q_num[next_n-1], next_n+1, current_score+q_num[next_n-1]*next_n*100+bonus[next_n-1], tyuuto_done)
    rec2(current_qn, next_n+1, current_score, tyuuto_done)
    if not tyuuto_done:
      for i in range(1,q_num[next_n-1]):
        rec2(current_qn+i, next_n+1, current_score+i*next_n*100, 1)

def rec(comb, next_n, current_score):
  if next_n == D + 1:
    global ans
    if current_score >= goal:
      ans = min(ans, sum(comb))
  else:
    for i in range(q_num[next_n-1]):
      rec(comb + [i], next_n+1, current_score + i * next_n * 100)
    rec(comb + [q_num[next_n-1]], next_n+1, current_score + q_num[next_n-1] * next_n * 100 + bonus[next_n-1])

# rec([], 1, 0)
rec2(0, 1, 0, 0)

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

import sys, itertools

n = int(sys.stdin.readline())
if n==1:
    print(0)
    quit()

MM = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

amin = 0
m = MM[0][:]
for i in range(n-1):
    amin += m[0]*m[1]*MM[i+1][1]
    m[1]=MM[i+1][1]


for t in itertools.permutations(range(n-1), n-2):

    mm=[m[:] for m in MM]
    o = list(t)
    ans=0
    for _ in range(n-2):
        i = o.pop(0)
        ans += mm[i][0]*mm[i+1][1]*mm[i][1]
        if ans>amin: break
        mm[i][1] = mm[i+1][1]
        mm.pop(i+1)
        
        for j in range(len(o)):
            if o[j]>i: o[j] -=1
    else:
        ans += mm[0][0]*mm[0][1]*mm[1][1]
        if amin>ans: amin=ans


print(amin)


### FIXED CODE ###

import sys

n = int(sys.stdin.readline())

m = list(map(int, sys.stdin.readline().split()))
for _ in range(n-1):
    _, a = sys.stdin.readline().split()
    m.append(int(a))

c = [[-1 for _ in range(n)] for _ in range(n)]

def val(a, b):
    if a==b: return 0
    if c[a][b]>0: return c[a][b]
    c[a][b]=val(a+1,b)+m[a-1]*m[a]*m[b]
    for k in range(a+1, b):
        v=val(a,k)+val(k+1,b)+m[a-1]*m[k]*m[b]
        if c[a][b]>v: c[a][b]=v
    return c[a][b]

print(val(0, n-1))
### BUGGY CODE ###

S = list(input())
Q = int(input())
cnt = 0
h = []
t = []
for i in range(Q):
  s = input().split()
  if s[0] == "1":
    cnt+=1
  elif s[0] == "2":
    if s[1] == "1":
      if cnt%2 == 0:        
        S.insert(0,s[2])
      else:
        S.append(s[2])
    elif s[1] == "2":
      if cnt%2==1:
        S.insert(0,s[2])       
      else:
        S.append(s[2])

if cnt%2 == 1:
  S = list(reversed(S))
  
print("".join(S))
  

### FIXED CODE ###

S = input()
Q = int(input())
b = "" #reversed
a = ""
f = 0
for i in range(Q):
  q = input()
  if q == "1":
    f+=1
  else:
    _,F,C = q.split()
    if (f+int(F))%2==1:
      b+=C
    else:
      a+=C
if f%2==0:
  print(b[::-1]+S+a)
else:
  print(a[::-1]+S[::-1]+b)
### BUGGY CODE ###

s = str(input())
length = len(s)
base = []
for i in range(length + 1):
  for j in range(i+3, length + 1):
    if int(s[i:j])%2019 == 0:
      base.append(s[i:j])
print(len(base))
      

### FIXED CODE ###

s = input()[::-1]
counts = [0]*2019
counts[0] = 1
sum = 0
d = 1
for c in s:
  sum += int(c)*d
  remain = sum%2019
  d *= 10
  d %= 2019
  counts[remain] += 1

ans = 0
for count in counts:
  ans += count*(count - 1) / 2
print(int(ans))
### BUGGY CODE ###

import numpy as np

N = int(input())
A = list(map(int,input().split()))
a = np.array([],dtype = int)
b = np.array([],dtype = int)

A = np.array(A)
ans = 0
for i in range(N-1):
    a = np.append(a,1-A[i])
    a = a + 1
    
a = a-1

for i in range(N):
    b = np.append(b,A[i])
    b = b + 1

b = b - 1


for i in b:
    ans += np.count_nonzero(a==i)


print(ans)
    

### FIXED CODE ###

import collections

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

L = [A[x]+x+1 for x in range(N)]
R = [x+1-A[x] for x in range(N)]

cL = collections.Counter(L)
cR = collections.Counter(R)

cRlist = list(cR.keys())

for i in range(len(cRlist)):
    tmp = cRlist[i]
    ans += cR.get(tmp,0) * cL.get(tmp,0)
    
print(ans)
### BUGGY CODE ###

N = int(input())

def f(n):
    flag = False
    #total = 0
    ans = 0
    i = 100
    for x in range(1,i):
        for y in range(1,i):
            for z in range(1,i):
                if (x + y + z)**2 - (x*y + y*z + x*z) == n:
                    #total += 1
                    flag = True
                    break
            if flag:
                break
        if flag:
            break
    if x == i-1:
        ans = 0
    elif x == y and  y== z:
        ans = 1
    elif x == y or y == z or x == z:
        ans = 3
    else:
        ans = 6
    return ans

for i in range(1,N+1):
    print(f(i))

### FIXED CODE ###

N = int(input())


ans = [0]*(N+1)
i = 102
for x in range(1,i):
    for y in range(1,i):
        for z in range(1,i):
            total = (x + y + z)**2 - (x*y + y*z + x*z)
            if total <= N:
                ans[total] += 1

for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

n,m=map(int,input().split())
dp=[0]*(n+1)
f=[]
dp[0]=1

for i in range(m):
    t=int(input())
    f.append(t)

for i in range(1,n+1):
    if i in f:
        continue
    else:
        if dp[i-1] != 0:
            dp[i] += dp[i-1]
        if i > 1:
            if dp[i-2] != 0:
                dp[i] += dp[i-2]

print(dp[-1]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
dp=[0]*(n+1)
f=[]
dp[0]=1

f=[True]*(n+1)
for _ in range(m):
    f[int(input())]=False

for i in range(1,n+1):
    if f[i]==False:
        continue
    else:
        if dp[i-1] != 0:
            dp[i] += dp[i-1]
        if i > 1:
            if dp[i-2] != 0:
                dp[i] += dp[i-2]

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

import sys
from collections import Counter 

N,*a = map(int,open(0).read().split())
for i in range(1<<N):
    bit_str = format(i,'b').zfill(N)
    r_bit_str = list(reversed(bit_str))
    flg = True
    ans = []
    for j in range(N):
        parts_bit = r_bit_str[j::j+1]
        c = Counter(parts_bit)
        sum1 = c["1"]
        if sum1 % 2 != a[j]:
            flg = False
            break
        elif a[j] == 1:
            ans.append(str(j+1))
    if flg:
        print(len(ans))
        print(" ".join(ans))
        sys.exit()
print(-1)  
    

### FIXED CODE ###

from collections import Counter

N,*a = map(int,open(0).read().split())
ans = []
for i in range(N)[::-1]:
    part_rem = sum(a[i::i+1]) % 2
    if a[i] == 0:
        if part_rem == 1:
            a[i] = abs(a[i] - 1) 
    elif a[i] == 1:
        if part_rem == 0:
            a[i] = abs(a[i] - 1)
            
c = Counter(a)            
print(c[1])
for i in range(N):
    if a[i] == 1:
        print(i+1,end=" ")
print()
### BUGGY CODE ###

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    prev=1
    cnt=0
    for i in range(k):
        prev*=a[i]
    for i in range(k,n):
        if i==0: continue
        crnt=prev/a[cnt]*a[i]
        if crnt > prev: print('Yes')
        else: print('No')
        prev=crnt
        cnt+=1
    return

if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    prev=1
    cnt=0
    for i in range(k,n):
        if i==0: continue
        prev=a[cnt]
        crnt=a[i]
        if crnt > prev: print('Yes')
        else: print('No')
        prev=crnt
        cnt+=1
    return

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  n = int(input())
  prev = -1
  nums = []
  table = {}

  for _ in range(n):
    v = int(input())

    if v != prev:
      nums.append(v)
      prev = v

  for i, n in enumerate(nums):
    if n not in table:
      table[n] = []

    table[n].append(i)

  values = [0] * len(nums)
  value = 1

  for i in range(len(nums)):
    values[i] += value

    for j in table[nums[i]]:
      if j <= i:
        continue

      values[j] += value

    value = values[i]

  print(value % int(1e+9 + 7), flush=True)


if __name__ == '__main__':
  main()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  value = 1
  skips = {}
  prev = -1

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

    if n == prev:
      continue

    prev = n

    if n in skips:
      value += skips[n]

    skips[n] = value

  print(value % int(1e+9 + 7), flush=True)


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

a,b,n=[int(x) for x in input().split()]

ma=0
for i in range(1,n+1):
    ma=max(ma,(i*a)//b-a*(i//b))
print(ma)

### FIXED CODE ###

a,b,n=[int(x) for x in input().split()]

i=min(b-1,n)
print((i*a)//b-a*(i//b))
### BUGGY CODE ###

k, s = map(int, input().split())
res = 0

for x in range(k+1):
  if x <= s:
    for y in range(k+1):
      if (x + y) <= s:
        for z in range(k+1):
          if (x + y + z) == s:
            res += 1
        
print(res)

### FIXED CODE ###

k, s = map(int, input().split())
res = 0

for x in range(k+1):
  for y in range(k+1):
    z = s - (x + y)
    if z >= 0 and z <= k:
      res += 1
        
print(res)