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

#!/usr/bin/env python3
import itertools

N = int(input().split()[0])
S = input()

index_list = [i for i in range(N)]
p_list = []

for pattern in itertools.combinations(index_list, 3):
    a, b, c = list(sorted(list(pattern)))

    s = S[a] + S[b] + S[c]
    p_list.append(s)

ans = len(set(p_list))

print(ans)


### FIXED CODE ###

import collections
import copy

N = int(input().split()[0])
S = input()

counter = collections.Counter(S)
total = 0
done_list = []

for i, ch in enumerate(S[::-1]):  # 3 * 10 ** 4
    if ch in done_list:
        counter[ch] = counter[ch] - 1
        if counter[ch] < 1:
            del counter[ch]
        continue
    sub_done_list = []
    counter[ch] = counter[ch] - 1
    if counter[ch] < 1:
        del counter[ch]
    sub_counter = copy.copy(counter)

    for ch_2 in S[N - (i + 1) - 1 :: -1]:  # 3 * 10 ** 4
        if ch_2 in sub_done_list:
            sub_counter[ch_2] = sub_counter[ch_2] - 1
            if sub_counter[ch_2] < 1:
                del sub_counter[ch_2]
            continue
        sub_done_list.append(ch_2)
        sub_counter[ch_2] = sub_counter[ch_2] - 1
        if sub_counter[ch_2] < 1:
            del sub_counter[ch_2]
        total += len(sub_counter.keys())

    done_list.append(ch)

ans = total

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

from collections import deque

H,W=map(int, raw_input().split() )
S=[ raw_input() for i in range(H) ] 


D=[ (1,0), (-1,0), (0,1), (0,-1) ] 


ret=0
q = deque([]) 


def dfs(x,y,current):
	ret=0
	V=[ [ 0 for i in range(W) ] for j in range(H) ]
	V[x][y]=1
	q.append( (x,y,current) )

	while q:
		x,y,current=q.pop()
		if S[x][y]==".":
			ret+=1

		for dx,dy in D:
			if 0<=x+dx<H and 0<=y+dy<W:
				if V[x+dx][y+dy]==0 and S[x+dx][y+dy] != current:
					if (x+dx, y+dy, S[x+dx][y+dy] ):
						V[x+dx][y+dy]=1
						q.append( (x+dx, y+dy, S[x+dx][y+dy] ) )
	return ret



ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#":
			ret=0
			q = deque([]) 
			V=[ [ 0 for i in range(W) ] for j in range(H) ]
			ans+=dfs(x,y, "#")

print ans


### FIXED CODE ###

from collections import deque

H,W=map(int, raw_input().split() )
S=[ raw_input() for i in range(H) ] 


D=[ (1,0), (-1,0), (0,1), (0,-1) ] 


V=[ [ 0 for i in range(W) ] for j in range(H) ]


def dfs(x,y,current):
	bc=0	#black count
	wc=0	#white count
	q = deque([]) 
	V[x][y]=1
	q.append( (x,y,current) )

	while q:
		x,y,current=q.popleft()

		if current == "#":	  bc+=1
		else:  wc+=1

		for dx,dy in D:
			if 0<=x+dx<H and 0<=y+dy<W:
				next=S[x+dx][y+dy] 
				if V[x+dx][y+dy]==0 and current !=next:
						V[x+dx][y+dy]=1
						q.append( (x+dx, y+dy,next) )

	return bc*wc




ans=0
for x in range(H):
	for y in range(W):
		if S[x][y]=="#" and V[x][y]==0:
			ans+=dfs(x,y, "#")

print ans
### BUGGY CODE ###

#n=int(input())
#a,b=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

sl=list(input())
q=int(input())
l=[list(map(str,input().split())) for i in range(q)]

#print(l)

count=0
isR=False
from collections import deque
for i in range(q):
    order=l[i]
    if order[0]=="1":
        count+=1
        #反転
    if count%2==0:
        isR=False
    else:
        isR=True
    if order[0]!="1":
        
        f=order[1]
        c=order[2]
        temp_f=f
        if isR:
            if temp_f=="1":
                temp_f="2"
            else:
                temp_f="1"
        if temp_f=="1":
            tempq=deque(sl)
            tempq.appendleft(c)
            sl=list(tempq)
        else:
            sl.append(c)
ln=len(sl)
ansl=[]
if isR:
    for i in range(ln-1,-1,-1):
        ansl.append(sl[i])
else:
    ansl=sl
ans=''.join(ansl)
print(ans)



### FIXED CODE ###

#n=int(input())
#a,b=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

sl=list(input())
q=int(input())
l=[list(map(str,input().split())) for i in range(q)]

#print(l)

count=0
isR=False
from collections import deque
sl=deque(sl)
for i in range(q):
    order=l[i]
    if order[0]=="1":
        count+=1
        #反転
    if count%2==0:
        isR=False
    else:
        isR=True
    if order[0]!="1":
        f=order[1]
        c=order[2]
        temp_f=f
        if isR:
            if temp_f=="1":
                temp_f="2"
            else:
                temp_f="1"
        if temp_f=="1":
            #tempq=deque(sl)
            sl.appendleft(c)
            #tempq.appendleft(c)
            #sl=list(tempq)
        else:
            sl.append(c)
sl=list(sl)
ln=len(sl)
ansl=[]
if isR:
    for i in range(ln-1,-1,-1):
        ansl.append(sl[i])
else:
    ansl=sl
ans=''.join(ansl)
print(ans)
### BUGGY CODE ###

N = int(input())
# print(N)
List = list(map(int, input().split()))
# print(List)

for i in range(N-1):
  print(List.count(i+1))
print(0)

### FIXED CODE ###

from collections import defaultdict
import collections

N = int(input())
List = list(map(int, input().split()))
# print(List)

# for i in range(N-1):
#   print(List.count(i+1))
# print(0)

c = collections.Counter(List)
# print(c)
for i in range(1,N+1):
  # print(i)
  print(c[i])
  # print()
### BUGGY CODE ###

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

#A.sort()
B.sort()
C.sort()

def is_ok(arg, target, abc):
    if abc[arg] > target:
        return True
    else:
        return False

def bict(left, right, target, abc):

    while(right - left > 1):
        mid = (right + left)//2

        if is_ok(mid, target, abc):
            right = mid
        else:
            left = mid

    return right

cnt = 0
for a in A:
    b_min_index = bict(-1, N, a, B)
    for b_index in range(b_min_index,N):
        c_min_index = bict(-1, N ,B[b_index],C)
        c_num = N - c_min_index
        cnt += c_num

print(cnt)


### FIXED CODE ###


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

A.sort()
B.sort()
C.sort()

def is_ok(arg, target, abc):
    if abc[arg] >= target:
        return True
    else:
        return False

def is_ok2(arg, target, abc):
    if abc[arg] > target:
        return True
    else:
        return False


def bict(left, right, target, abc, jug):

    while(right - left > 1):
        mid = (right + left)//2

        if jug(mid, target, abc):
            right = mid
        else:
            left = mid

    return right

cnt = 0
for b in B:
    a_min_index = bict(-1, N, b, A, is_ok)
    c_min_index = bict(-1, N, b, C, is_ok2)
    temp = (a_min_index - 1 + 1) * (N - c_min_index)
    cnt += temp

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

'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

for i in range(M):
	x, y, z = map(int,input().split())
	x = x - 1
	y = y - 1
	A[x].append(y)
	A[y].append(x)

cost = 0
for i in range(N):
	if c[i] == 0:
		cost = cost + 1
		q.append(i)
		while len(q):
			j = q.pop(0)
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)


### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

for i in range(M):
	x, y, z = map(int,input().split())
	x = x - 1
	y = y - 1
	A[x].append(y)
	A[y].append(x)

cost = 0
for i in range(N):
	if c[i] == 0:
		cost += 1
		q.append(i)
		while len(q):
			j = q.pop()
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)
### BUGGY CODE ###

import sys
import heapq
import copy


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


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

mx = None

for i in range(N+1):
    h1 = A[0:N+i]
    h2 = A[N+i:N*3]

    heapq.heapify(h1)
    heapq._heapify_max(h2)

    for k in range(N):
        if i <= k:
            _heappop_max(h2)
        else:
            heapq.heappop(h1)

    s = sum(h1) - sum(h2)

    if (mx == None or s > mx):
        mx = s

print(mx)


### FIXED CODE ###

import sys
import heapq
import copy


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


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

sum_h1 = [0] * (N+1)
sum_h2 = [0] * (N+1)

'''
N=2
0 1 2 3 4 5 6
3 1 4 1 5 9
'''

h1 = A[0:N]
h2 = A[N*2:N*3]

heapq.heapify(h1)
heapq._heapify_max(h2)

#print("h1", h1)
#print("h2", h2)
sum_h1[0] = sum(h1)
sum_h2[N] = sum(h2)

for k in range(N):
    #print("A[N+k]", A[N+k])
    #print("k+1", k+1)

    sum_h1[k+1] = sum_h1[k]
    sum_h1[k+1] += A[N+k]
    a = heapq.heappushpop(h1, A[N+k])
    sum_h1[k+1] -= a

    #sum_h1[k+1] = sum(h1)

    #print("A[2*N-k-1]", A[2*N-k-1])
    #print("N-k-1", N-k-1)

    sum_h2[N-k-1] = sum_h2[N-k]
    sum_h2[N-k-1] += A[2*N-k-1]
    _heappush_max(h2, A[2*N-k-1])
    sum_h2[N-k-1] -= _heappop_max(h2)

    #sum_h2[N-k-1] = sum(h2)


mx = None

#print("sum_h1", sum_h1)
#print("sum_h2", sum_h2)

for i in range(N+1):
    a = sum_h1[i] - sum_h2[i]

    if(mx == None or a > mx):
        mx = a

print(mx)

'''
for i in range(N+1):
    h1 = A[0:N+i]
    h2 = A[N+i:N*3]

    heapq.heapify(h1)
    heapq._heapify_max(h2)

    for k in range(N):
        if i <= k:
            _heappop_max(h2)
        else:
            heapq.heappop(h1)

    s = sum(h1) - sum(h2)

    if (mx == None or s > mx):
        mx = s
'''
### BUGGY CODE ###

n = int(input())
p = 10**9 + 7
def check(L4):
  for i in range(4):
    t = list(L4)
    if i > 0:
      t[i], t[i-1] = t[i-1], t[i]
    if "".join(t).count("AGC") >= 1:
      return False
  return True
def dfs(d, L3):
  if d >= n:
    return 1
  ret = 0
  for L in list("ACGT"):
    L4 = "".join([L3, L])
    if check(L4):
      ret += dfs(d + 1, L4[1:])
  return ret
    
  
  
print(dfs(0, "TTT"))

### FIXED CODE ###

n = int(input())
p = 10**9 + 7
memo = [{} for _ in range(n+1)]
def check(L4):
  for i in range(4):
    t = list(L4)
    if i > 0:
      t[i], t[i-1] = t[i-1], t[i]
    if "".join(t).count("AGC") >= 1:
      return False
  return True
def dfs(d, L3):
  if L3 in memo[d]:
    return memo[d][L3]
  if d >= n:
    return 1
  ret = 0
  for L in list("ACGT"):
    L4 = L3 + L
    if check(L4):
      ret += dfs(d + 1, L4[1:]) 
    memo[d][L3] = ret
  return ret % p
    
  
  
print(dfs(0, "TTT"))
### BUGGY CODE ###

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int,ss_raw()))

X,Y,Z,K = ints_raw()

A = ints_raw()
B= ints_raw()
C= ints_raw()
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
def main():
    D = []
    for a in A:
        for b in B:
            D.append(a+b)
    D.sort(reverse=True)
    D = D[:K]
    E =[]
    for d in D:
        for c in C:
            E.append(d+c)
    E.sort(reverse=True)
    for e in E[:K]:
        print (e)

main()


### FIXED CODE ###

from heapq import *

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int,ss_raw()))

X,Y,Z,K = ints_raw()

A = ints_raw()
B= ints_raw()
C= ints_raw()
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

arg_hash = {}

def main():
    Q = []
    heappush(Q,(-A[0]-B[0]-C[0],0,0,0))
    arg_hash[(0,0,0)]=1
    for k in range(K):
        ans = heappop(Q)
        print(-ans[0])
        a,b,c = ans[1:]

        argA = (a+1,b,c)
        if a < X-1 and (not argA in arg_hash):
            arg_hash[argA]=1
            heappush(Q,(-A[a+1]-B[b]-C[c],)+argA)
        argB = (a,b+1,c)
        if b < Y-1 and (not argB in arg_hash):
            arg_hash[argB]=1
            heappush(Q, (-A[a]-B[b+1]-C[c],)+argB)
        argC = (a,b,c+1)
        if c < Z-1 and (not argC in arg_hash):
            arg_hash[argC]=1
            heappush(Q,(-A[a]-B[b]-C[c+1],)+argC)
        
main()
### BUGGY CODE ###

from functools import reduce
n = int(input())
tab = [int(i) for i in input().split()]

if reduce(lambda x, y: x*y, tab) > pow(10, 18):
  print("-1")
else:
  print(reduce(lambda x, y: x*y, tab))

### FIXED CODE ###

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

from collections import deque

n = int(input())

q = deque()

list2 = [input().split(" ") for _ in range(n)]

for lst in list2:

	if lst[0] == "insert":
		q.appendleft(int(lst[1]))
	elif lst[0] == "delete":
		if q.count(int(lst[1])) != 0:
			q.remove(int(lst[1]))
	elif lst[0] == "deleteFirst":
		q.popleft()
	elif lst[0] == "deleteLast":
		q.pop()

print(*q)



### FIXED CODE ###

from collections import deque
from sys import stdin

n = int(input())

q = deque()

for _ in range(n):
	cmd = stdin.readline().strip().split()
	if cmd[0] == "insert":
		q.appendleft(cmd[1])
	elif cmd[0] == "deleteFirst":
		q.popleft()
	elif cmd[0] == "deleteLast":
		q.pop()
	elif cmd[0] == "delete":
		try:
			q.remove(cmd[1])
		except:
			pass

print(*q)
### BUGGY CODE ###

from functools import reduce


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


'''
def lcm(a, b):
    return a * b // gcd(a, b)
'''
n = int(input())
a_list = list(map(int, input().split()))
remove_list = a_list[:]
re_max = 0

for i in range(len(a_list)):
    remove_list.pop(i)
    re_max = max(re_max, reduce(gcd, remove_list))
    remove_list = a_list[:]

print(re_max)



### FIXED CODE ###

from functools import reduce


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    return a * b // gcd(a, b)


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

l = [0 for i in range(n)]
for i in range(0, n - 1, 1):
    l[i + 1] = gcd(l[i], a[i])

r = [0 for i in range(n)]
for i in range(n - 2, -1, -1):
    r[i] = gcd(r[i + 1], a[i + 1])

m = [gcd(l[i], r[i]) for i in range(n)]

print(reduce(max, m))
### BUGGY CODE ###

l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	l.append([item[1],item[0]])

# n=4
# l=[[2,3],[1,2],[3,4],[2,2]] #w,v
# W=5

def solve(i,w):
	if i==n:
		return(0)
	elif w-l[i][0]<0:
		return(solve(i+1,w))
	else:
		a=solve(i+1,w)
		b=l[i][1]+solve(i+1,w-l[i][0])
		if b>a:
			return(b)
		else:
			return(a)

print(solve(0,W))

### FIXED CODE ###

value=[0]
weight=[0]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	value.append(item[0])
	weight.append(item[1])

dp=[[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	for j in range(W+1):
		if i==0:
			res=0
		elif j-weight[i]<0:
			res=dp[i-1][j]
		else:
			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
		dp[i][j]=res
print(dp[n][W])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [sys.maxsize]*N
dp[0], dp[1] = 0, abs(H[0]-H[1])

for i in range(2, N):
  dp[i] = min(dp[i-k] + abs(H[i]-H[i-k]) for k in range(1,K+1))
print(dp[-1])    

### FIXED CODE ###

import sys
input = sys.stdin.readline

def cmin(a, b, i):
  if a > b:
    dp[i] = b
    return True
  return False

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [sys.maxsize]*N
dp[0] = 0

for i in range(0, N):
  for j in range(1,K+1):
    cmin(dp[i], dp[i-1] + abs(h[i] - h[i-1]), i)
    if i > 1:
      cmin(dp[i], dp[i-j] + abs(h[i] - h[i-j]), i)
print(dp[N-1])
### BUGGY CODE ###

n = int(input())
s = list(input())
total = 0
for i in range(1000):
  t = list(str(i).zfill(3))
  j = 0
  for c in range(len(s)):
    if (j<=len(t)-1):
      if(s[c] == t[j]):
        j += 1
  if (j == 3):
    total += 1
print(total)

### FIXED CODE ###

n = int(input())
s = list(input())
total = 0
for i in range(1000):
  t = list(str(i).zfill(3))
  j = 0
  for c in range(len(s)):
    if (j<=len(t)-1):
      if(s[c] == t[j]):
        j += 1
  if (j == 3):
    total += 1
print(total)
### BUGGY CODE ###

Q = int(input())
mod = int(1e+6 + 3)

def doubling(n, m):
  y = 1
  p = n
  while m != 0:
    if m % 2 == 1:
      y *= p
      y %= mod
    m //= 2
    p *= p
    p %= mod
  return y

def inved(s):
  x, y, u, v, k, l = 1, 0, 0, 1, s, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod

frac = [1 for _ in range(mod+1)]
invf = [1 for _ in range(mod+1)]
invf[mod] = 0
for i in range(mod):
  frac[i+1] = (frac[i] * (i+1)) % mod
invf[mod-1] = inved(frac[mod-1])
for i in range(mod-1, 0, -1):
  invf[i-1] = (invf[i] * i) % mod

for i in range(Q):
  x, d, n = map(int, input().split())
  if x == 0:
    print(0)
  else:
    if d == 0:
      print(doubling(x, n))
    else:
      if n >= mod:
        print(0)
      else:
        xinvd = x * inved(d) - 1
        xinvd %= mod
        if xinvd + n >= mod:
          print(0)
        else:
          dn = doubling(d, n)
          print((dn * frac[xinvd + n] * invf[xinvd]) % mod)

### FIXED CODE ###

Q = int(input())
mod = int(1e+6 + 3)

def doubling(n, m):
  y = 1
  p = n
  while m != 0:
    if m % 2 == 1:
      y *= p
      y %= mod
    m //= 2
    p *= p
    p %= mod
  return y

def inved(s):
  x, y, u, v, k, l = 1, 0, 0, 1, s, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod

frac = [1 for _ in range(mod+1)]
invf = [1 for _ in range(mod+1)]
invf[mod] = 0
for i in range(mod):
  frac[i+1] = (frac[i] * (i+1)) % mod
invf[mod-1] = inved(frac[mod-1])
for i in range(mod-1, 0, -1):
  invf[i-1] = (invf[i] * i) % mod

for i in range(Q):
  x, d, n = map(int, input().split())
  if x == 0:
    print(0)
  else:
    if d == 0:
      print(doubling(x, n))
    else:
      if n >= mod:
        print(0)
      else:
        xinvd = x * inved(d) - 1
        xinvd %= mod
        if xinvd + n >= mod:
          print(0)
        else:
          dn = doubling(d, n)
          print((dn * frac[xinvd + n] * invf[xinvd]) % mod)
### BUGGY CODE ###

import sys
import functools

@functools.lru_cache(maxsize=20000)
def popcount(n):
    return '{:b}'.format(n).count('1')


def f(n):
    i = 0
    # print(f'{n=}')
    while n:
        i += 1
        n = n % popcount(n)
    return i


def resolve(in_):
    n = int(in_.readline())
    x = int(in_.readline(), 2)
    for i in range(n - 1, -1, -1):
        v = x ^ (1 << i)
        # print(f'{x=} {v=} {1<<n=}')
        print(f(v))


def main():
    resolve(sys.stdin.buffer)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys


def popcount(n):
    c = 0
    while n:
        if n & 1:
            c += 1
        n >>= 1

    return c


def f(n, c=0):
    while pc := popcount(n):
        n %= pc
        c += 1

    return c


def _resolve(n, x_bytes):
    one_i = b'1'[0]
    pc_x = x_bytes.count(b'1')

    i2_mod_pc_x_p1 = [0] * n
    i2_mod_pc_x_m1 = [0] * n
    x_mod_pc_x_p1 = 0
    x_mod_pc_x_m1 = 0

    i2 = 1
    x = 0
    mod = pc_x + 1
    for a in range(n):
        i2_mod_pc_x_p1[- 1 - a] = i2
        i2 *= 2
        i2 %= mod

        x *= 2
        x %= mod
        if (x_bytes[a] == one_i):
            x += 1
    x_mod_pc_x_p1 = x % mod

    if pc_x > 1:
        i2 = 1
        x = 0
        mod = pc_x - 1
        for a in range(n):
            i2_mod_pc_x_m1[- 1 - a] = i2
            i2 *= 2
            i2 %= mod

            x *= 2
            x %= mod
            if (x_bytes[a] == one_i):
                x += 1
        x_mod_pc_x_m1 = x % mod

    # print(pc_x)
    # print(x_mod_pc_x_p1)
    # print(x_mod_pc_x_m1)

    # print(i2_mod_pc_x_p1)
    # print(i2_mod_pc_x_m1)

    for a in range(n):
        if x_bytes[a] == one_i:
            mod = pc_x - 1
            if mod == 0:
                yield 0
                continue
            b = x_mod_pc_x_m1 - i2_mod_pc_x_m1[a]
        else:
            mod = pc_x + 1
            b = x_mod_pc_x_p1 + i2_mod_pc_x_p1[a]
        b %= mod

        yield f(b, 1)

def resolve(in_, out):
    n = int(in_.readline())
    x_bytes = in_.readline()
    for ret in _resolve(n, x_bytes):
        print(ret, file=out)


def main():
    resolve(sys.stdin.buffer, sys.stdout)


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

A,B,N=[int(x) for x in input().rstrip().split()]
ans=0
now=0
aa=0

cnt=0
while(True):
  if 0<int(cnt/B):
    break
  else:
    cnt+=1
cnt=cnt-1

if N<B:
  print(int(A*N/B)-A*int(N/B))
else:
  print(int(A*cnt/B)-A*int(cnt/B))


### FIXED CODE ###

A,B,N=[int(x) for x in input().rstrip().split()]
ans=0
now=0
aa=0

cnt=0

if N<B:
  print(int(A*N/B)-A*int(N/B))
else:
  print(int(A*(B-1)/B)-A*int((B-1)/B))
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
aa = inpl()

def calc(x):
	aa_dush = [-1]*N
	for i in range(N):
		if aa[i] >= x:
			aa_dush[i] = 1
	#aa_dush = [1, 1, 1, 1, 1, 1, -1, 1, -1, -1]

	S = [0] #S_0 = 0を忘れずにつける
	tmp = 0
	MIN = MAX = 0
	for i in range(N):
		tmp += aa_dush[i]
		MIN = min(tmp,MIN)
		MAX = max(tmp,MAX)
		S.append(tmp)
	#S = [0, 1, 2, 3, 4, 5, 6, 5, 6, 5, 4]
	#MIN = 0 , MAX = 6

	L = (MAX-MIN+1) #BITのサイズ L=6
	bit = [0]*(L+1) #1indexで扱うのでL+1の長さで取る
	ans = 0
	for S_i in S:
		S_i -= (MIN-1) #S_iの最小値が1となるように調整

		#BITで既出の要素のうちS_i以下の要素数をカウント
		tmp = 0
		x = S_i
		while x > 0:
			tmp += bit[x]
			x -= x & -x
		ans += tmp

		#BITのS_iに1を加算して更新
		x = S_i
		while x <= L:
			bit[x] += 1
			x += x & -x

	return ans #中央値がx以上となる(l,r)の組の数

border = ( (N+1)*N//2 +1 )//2
OK = 0
NG = 10**9+3

while NG - OK > 1:
	mid = (OK+NG)//2
	if calc(mid) >= border:
		OK = mid
	else:
		NG = mid

print(OK)


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
aa = inpl()

def calc(x):
	aa_dush = [-1]*N
	for i in range(N):
		if aa[i] >= x:
			aa_dush[i] = 1
	#aa_dush = [1, 1, 1, 1, 1, 1, -1, 1, -1, -1]

	S = [0] #S_0 = 0を忘れずにつける
	tmp = 0
	MIN = MAX = 0
	for i in range(N):
		tmp += aa_dush[i]
		MIN = min(tmp,MIN)
		MAX = max(tmp,MAX)
		S.append(tmp)
	#S = [0, 1, 2, 3, 4, 5, 6, 5, 6, 5, 4]
	#MIN = 0 , MAX = 6

	L = (MAX-MIN+1) #BITのサイズ L=6
	bit = [0]*(L+1) #1indexで扱うのでL+1の長さで取る
	ans = 0
	for S_i in S:
		S_i -= (MIN-1) #S_iの最小値が1となるように調整

		#BITで既出の要素のうちS_i以下の要素数をカウント
		tmp = 0
		x = S_i
		while x > 0:
			tmp += bit[x]
			x -= x & -x
		ans += tmp

		#BITのS_iに1を加算して更新
		x = S_i
		while x <= L:
			bit[x] += 1
			x += x & -x

	return ans #中央値がx以上となる(l,r)の組の数

border = ( (N+1)*N//2 +1 )//2
OK = 0
NG = 10**9+3

while NG - OK > 1:
	mid = (OK+NG)//2
	if calc(mid) >= border:
		OK = mid
	else:
		NG = mid

print(OK)