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

n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    s1 = s[l-1:r].replace("AT", " ")
    s2 = s1.replace("AG", " ")
    s3 = s2.replace("TC", " ")
    s4 = s3.replace("TG", " ")
    print(s4.count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

t = [0] * (N)
for i in range(N-1):
    t[i+1] = t[i] + (1 if S[i:i+2]=="AC" else 0)

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

h, n = map(int, input().split())
a, b = [], []
for _ in range(n):
    _a, _b = map(int, input().split())
    a.append(_a)
    b.append(_b)

dp = [[float("inf")]*(h+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][min(j+a[i], h)] = min(dp[i+1][min(j+a[i], h)], dp[i+1][j] + b[i])

print(dp[n][h])


### FIXED CODE ###

h, n = map(int, input().split())
a, b = [], []
for _ in range(n):
    _a, _b = map(int, input().split())
    a.append(_a)
    b.append(_b)

dp = [[float("inf")]*(h+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(h+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][min(j+a[i], h)] = min(dp[i+1][min(j+a[i], h)], dp[i+1][j] + b[i])

print(dp[n][h])
### BUGGY CODE ###


N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())

INF = 10 ** 9 + 7
d = [[INF] * 3 for _ in range(N + 1)]
d[S][0] = 0
for _ in range(M):
    for u, v in X:
        for i in range(3):
            if d[u][i] < INF and d[v][(i + 1) % 3] > d[u][i] + 1:
                d[v][(i + 1) % 3] = d[u][i] + 1

if d[T][2] == INF:
    print(-1)
else:
    print(d[T][2])


### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(M)]
S, T = map(int, input().split())

graph = [[] for _ in range(N + 1)]
for u, v in edges:
    graph[u].append(v)

INF = 10 ** 9 + 7
dp = [[INF] * (N + 1) for _ in range(3)]
dp[0][S] = 0
q = deque()
q.append((S, 0))

while q:
    v, t = q.popleft()
    u = (t + 1) % 3
    d = dp[t][v]
    if t == 2:
        d += 1
    for w in graph[v]:
        if dp[u][w] != INF:
            continue
        dp[u][w] = d
        q.append((w, u))
        
print(dp[0][T] if dp[0][T] < INF else -1)
### BUGGY CODE ###

import numpy as np

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

ans = 0
while len(A) > 0:
    if len(A) == 1:
        ans += 1
    elif A[0] != A[1]:
        ans += 1
    n = A[0]
    A = A[np.where(A % n != 0)[0]]
    
print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(i) for i in input().split()]
num = set(A)
count = Counter(A)
dp = [True] * (10**6 + 1)

for a in num:
    for n in range(a+a, 10**6+1, a):
        dp[n] = False

ans = 0
for a in num:
    if count[a] == 1 and dp[a] == True:
        ans += 1

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

def isprime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return x!=1
def sieve(m):
    n=1
    primes = {}
    arr=set([])
    for i in range(2, int(m ** 0.5) + 1):
        a = n // i
        b = m // i
        for k in range(max(2, a), b + 1):
            c = i * k
            primes[c] = 1

    for i in range(max(n, 2), m + 1):
        if i not in primes:
            arr.add(i)

    return arr
arr=sieve(10**7)
dic={}
n=int(input())

if isprime(n):
    print(1)
    exit()
for i in arr:
    if n%i==0:
        cnt=0
        while n%i==0:
            cnt+=1
            n//=i
        dic[i]=cnt
ans=0
for i in dic:
    x=dic[i]
    r=(-1+(1+8*x)**0.5)//2
    ans+=r
print(int(ans))




### FIXED CODE ###

def isprime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return x!=1


dic={}
n=int(input())
t=int(n**0.5)+1
for i in range(2,t):
    cnt=0
    while n%i==0:
        cnt+=1
        n//=i
    dic[i]=cnt
if n!=1:
    dic[n]=1
ans=0
for i in dic:
    x=dic[i]
    r=(-1+(1+8*x)**0.5)//2
    ans+=r
print(int(ans))
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
ax = [int(_) for _ in input().split()]
ay = [int(_) for _ in input().split()]
az = [int(_) for _ in input().split()]
ax.sort(reverse=True)
ay.sort(reverse=True)
az.sort(reverse=True)
INF = - 3 *10 ** 10
ax.extend([INF]*k)
ay.extend([INF]*k)
az.extend([INF]*k)
l = [(ax[0]+ay[0]+az[0],0,0,0)]
for i in range(k):
    t = l.pop(0)
    print(t[0])
    if (ax[t[1]+1]+ay[t[2]]+az[t[3]],t[1]+1,t[2],t[3]) not in l:
        l.append((ax[t[1]+1]+ay[t[2]]+az[t[3]],t[1]+1,t[2],t[3]))
    if (ax[t[1]]+ay[t[2]+1]+az[t[3]],t[1],t[2]+1,t[3]) not in l:
        l.append((ax[t[1]]+ay[t[2]+1]+az[t[3]],t[1],t[2]+1,t[3]))    
    if (ax[t[1]]+ay[t[2]]+az[t[3]+1],t[1],t[2],t[3]+1) not in l:
        l.append((ax[t[1]]+ay[t[2]]+az[t[3]+1],t[1],t[2],t[3]+1))
    l.sort(key=lambda x:(-x[0],x[1],x[2],x[3]))

### FIXED CODE ###

import heapq
x,y,z,k = map(int,input().split())
ax = [int(_) for _ in input().split()]
ay = [int(_) for _ in input().split()]
az = [int(_) for _ in input().split()]
ax.sort(reverse=True)
ay.sort(reverse=True)
az.sort(reverse=True)
INF = - 3 *10 ** 10
ax.extend([INF])
ay.extend([INF])
az.extend([INF])
l = [(-(ax[0]+ay[0]+az[0]),0,0,0)]
checked = {(-(ax[0]+ay[0]+az[0]),0,0,0)}
for i in range(k):
    t = heapq.heappop(l)
    print(-t[0])
    if (-(ax[t[1]+1]+ay[t[2]]+az[t[3]]),t[1]+1,t[2],t[3]) not in checked:
        heapq.heappush(l,(-(ax[t[1]+1]+ay[t[2]]+az[t[3]]),t[1]+1,t[2],t[3])) 
        checked.add((-(ax[t[1]+1]+ay[t[2]]+az[t[3]]),t[1]+1,t[2],t[3]))
    if (-(ax[t[1]]+ay[t[2]+1]+az[t[3]]),t[1],t[2]+1,t[3]) not in checked:
        heapq.heappush(l,(-(ax[t[1]]+ay[t[2]+1]+az[t[3]]),t[1],t[2]+1,t[3]))
        checked.add((-(ax[t[1]]+ay[t[2]+1]+az[t[3]]),t[1],t[2]+1,t[3]))
    if (-(ax[t[1]]+ay[t[2]]+az[t[3]+1]),t[1],t[2],t[3]+1) not in checked:
        heapq.heappush(l,(-(ax[t[1]]+ay[t[2]]+az[t[3]+1]),t[1],t[2],t[3]+1))
        checked.add((-(ax[t[1]]+ay[t[2]]+az[t[3]+1]),t[1],t[2],t[3]+1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d1 = []
d2 = []
for i in range(3):
  if a[i] < b[i]: d1.append((a[i], b[i]))
  if a[i] > b[i]: d2.append((b[i], a[i]))

dp = [0] * (N + 1)

for i in range(N, -1, -1):
  for t in d1:
    x = t[0]
    y = t[1]
    if i - x >= 0:
      dp[i - x] = max(dp[i - x], y + dp[i])
for i in range(N + 1): dp[i] += i
res1 = max(dp)
#print(dp)
dp2 = [0] * (res1 + 1)
for i in range(res1, -1, -1):
  for t in d2:
    x = t[0]
    y = t[1]
    if i - x >= 0:
      dp2[i - x] = max(dp2[i - x], y + dp2[i])
for i in range(res1 + 1): dp2[i] += i
print(max(dp2))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d1 = []
d2 = []
for i in range(3):
  if a[i] < b[i]: d1.append((a[i], b[i]))
  if a[i] > b[i]: d2.append((b[i], a[i]))

dp = [0] * (N + 1)

for i in range(N, -1, -1):
  for t in d1:
    x = t[0]
    y = t[1]
    if i - x >= 0:
      dp[i - x] = max(dp[i - x], y + dp[i])
for i in range(N + 1): dp[i] += i

def calc(x, r1):
  z = r1 - d2[0][0] * x
  return (z // d2[1][0]) * d2[1][1] + z % d2[1][0] + d2[0][1] * x

res1 = max(dp)
if len(d2) == 0:
  print(res1)
if len(d2) == 1:
  x, y = d2.pop()
  print((res1 // x) * y + (res1 % x))
if len(d2) == 2:
  x0 = 0
  x3 = res1 // d2[0][0]
  res2 = res1 + 0
  for x in range(x0, x3 + 1):
    res2 = max(res2, calc(x, res1))
  print(res2)

if len(d2) == 3:
  dp2 = [0] * (res1 + 1)
  for i in range(res1, -1, -1):
    for t in d2:
      x = t[0]
      y = t[1]
      if i - x >= 0:
        dp2[i - x] = max(dp2[i - x], y + dp2[i])
  for i in range(res1 + 1): dp2[i] += i
  print(max(dp2))
### BUGGY CODE ###

def comb(n, k):
    ret = 1
    for i in range(k):
        ret *= (n-i)
        ret //= (i+1)
    return ret

n = int(input())
a = [ int(x) for x in input().split() ]
a.sort(reverse=True)

n, r = a[0], a[1]
t = -1
for aa in a[1:]:
    if comb(n, aa) >= t:
        r = aa
        t = comb(n, aa)

print(n, r)



### FIXED CODE ###

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

a.sort(reverse=True)

n = a[0]
r = -1
t = a[0]
for aa in a[1:]:
    if abs(n/2-aa) <= t:
        r = aa
        t = abs(n/2-aa)

print(n, r)
### BUGGY CODE ###

N, M = map(int, input().split())
A_array = list(map(int, input().split()))
A_array.sort()
BC_array = [list(map(int, input().split())) for _ in range(M)]
BC_array = sorted(BC_array, key=lambda x: x[1])
# print(A_array, BC_array)

for B, C in BC_array:
    for i in range(B):
        if A_array[i] < C:
            A_array[i] = C
        else:
            break
    A_array.sort()

print(sum(A_array))

### FIXED CODE ###

N, M = map(int, input().split())
A_array = sorted(map(int, input().split()))
BC_array = [list(map(int, input().split())) for _ in range(M)]
BC_array = sorted(BC_array, key=lambda x: x[1])

plus_count = 0
ans = 0
a_index = N - 1
bc_index = M - 1

while plus_count != N:
    if A_array[a_index] <= BC_array[bc_index][1]:
        add_count = min(BC_array[bc_index][0], N - plus_count)
        plus_count += add_count
        ans += (add_count * BC_array[bc_index][1])
        bc_index -= 1
        if bc_index < 0:
            a_rest = N - plus_count
            ans += sum(A_array[a_index - a_rest + 1:a_index + 1])
            break
    else:
        plus_count += 1
        ans += A_array[a_index]
        a_index -= 1
print(ans)
### BUGGY CODE ###

H, W = [int(x) for x in input().split()]

cnt = 0
for h in range(1, H+1):
    for w in range(1, W + 1):
        if h % 2 == 1 and w % 2 == 1:
            cnt += 1
        elif h % 2 == 0 and w % 2 == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

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

if H==1 or W==1:
    print(1)
elif H%2==0:
    print(W*(H//2))
else:
    print(W*(H//2) + (W+1)//2)
### BUGGY CODE ###

N,Q = input().split(" ")
sentence = input()

for i in range(int(Q)):
	count = 0
	l,r = input().split(" ")
	l = int(l)
	r = int(r)
	for j in range(r-l):
		if sentence[l-1+j] == "A":
			if sentence[l+j] == "C":
				count += 1
	print(count)

### FIXED CODE ###

N,Q = map(int, input().split(" "))
sentence = input()

"""
###文章そのままの実装ー＞N,Q によりオーダーが大きくなりすぎる
for i in range(int(Q)):
	count = 0
	l,r = map(int, input().split(" "))
	for j in range(r-l):
		if sentence[l-1+j:l+j+1] == "AC":
			count += 1
	print(count)

"""

###累積和を用いて高速に計算
#予め累積和を計算　クエリで高速回答
#ACACTGC
#0112222
AC_list = [0]*(N)
count = 0
for i in range(N-1):
	if sentence[i : i+2] == "AC":
		count += 1
	AC_list[i+1] = count

for i in range(Q):
	l,r = map(int, input().split())
	print(AC_list[r-1]-AC_list[l-1])
### BUGGY CODE ###


a,b,n=map(int,input().split())
m=0
for i in range(1,n+1):
    s=i/b
    num=int(a*s)
    num-=a*int(s)
    if num>=m:
        m=num
    
print(m)

### FIXED CODE ###

a,b,n=map(int,input().split())
if b>n:
    print(int(a*n/b)-a*int(n/b))
else:
    print(int(a*(b-1)/b)-a*int((b-1)/b))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for k in range(len(A)):
  ans = 0
  search = A.copy()
  search.pop(k)
  unique = set(search)
  for u in unique:
    c = search.count(u)
    ans += c * (c-1) / 2
  print(int(ans))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
import collections

c = collections.Counter(l)
ans=0
for v in c.values():
  ans+=v*(v-1)//2

for x in l:
  print(ans-c[x]+1)
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [0]*(W+1)

for i in range(0, N):
    wi, vi = map(int, input().split())
    dp_next = [0] * (W+1)
    for w in range(1, W+1):
        if w >= wi:
            dp_next[w] = max(dp[w - wi] + vi, dp[w])
        else:
            dp_next[w] = dp[w]
    dp = dp_next
print(dp[-1])

### FIXED CODE ###

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

N, W = map(int, input().split())
dp = np.zeros((N, W+1), dtype='int64')

def solve(N, W):
    for i in range(0, N):
        wi, vi = map(int, input().split())
        dp[i][:wi] = dp[i-1][:wi]
        dp[i][wi:] = np.fmax(dp[i-1][wi:],
                            dp[i-1][:W+1-wi] + vi)
    return dp[N-1][W]

print(solve(N, W))
### BUGGY CODE ###

A, B, N = map(int, input().split())
ans = 0
for x in range(1, N+1):
    now = (A*x)//B - A*(x//B)
    ans = max(now, ans)
print(ans)

### FIXED CODE ###

A, B, N = map(int, input().split())
x = min(B-1, N)

ans = int(A*x/B) - A*int(x/B)
print(ans)
### BUGGY CODE ###


H,W,K = map(int,input().split())

A = []
for i in range(H):

    a = list(map(int,list(input())))
    A.append(a)

#print (A)
ans = float("inf")

for i in range(2**(H-1)):

    wtk = [0]
    cut = 0

    for j in range(H-1):

        if i & 2**j > 0:
            wtk.append(wtk[-1]+1)
            cut += 1
        else:
            wtk.append(wtk[-1])

    now = [0] * (H)

    for y in range(W):

        flag = True
        nnow = now.copy()
        save = [0] * (H)

        for x in range(H):

            nnow[wtk[x]] += A[x][y]
            save[wtk[x]] += A[x][y]

        if max(save) > K:
            cut = float("inf")
            break
        if max(nnow) > K:
            cut += 1
            nnow = save

        now = nnow

    ans = min(ans,cut)
            
print (ans)


### FIXED CODE ###


H,W,K = map(int,input().split())

A = []
for i in range(H):

    a = list(map(int,list(input())))
    A.append(a)

#print (A)
ans = float("inf")

for i in range(2**(H-1)):

    wtk = [0]
    cut = 0

    for j in range(H-1):

        if i & 2**j > 0:
            wtk.append(wtk[-1]+1)
            cut += 1
        else:
            wtk.append(wtk[-1])

    now = [0] * (H)

    for y in range(W):

        flag = True
        nnow = []
        for ll in now:
            nnow.append(ll)
        save = [0] * (H)

        for x in range(H):

            nnow[wtk[x]] += A[x][y]
            save[wtk[x]] += A[x][y]

        if max(save) > K:
            cut = float("inf")
            break
        if max(nnow) > K:
            cut += 1
            nnow = save

        now = nnow

    ans = min(ans,cut)
            
print (ans)
### BUGGY CODE ###

n = int(input())
res = 0
for i in range(1, n, 1):
    res += i
print(res)

### FIXED CODE ###

n = int(input())
print((n*(n-1)//2))
### BUGGY CODE ###

# UnionTreeクラス：グループ分けを木構造で管理する
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.root(self.par[x])

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]


def output(uf):
    count = 0
    for i in range(uf.N):
        sub_par = uf.par[i+1:]
        count += len(sub_par) - sub_par.count(uf.par[i])

    return count
    
n, m = (int(i) for i in input().split())
input_arr = [[int(i) for i in input().split()] for i in range(m)] 

uf = UnionFind(n)
#input_arr = [[1,2],[3,4],[1,3],[2,3],[1,4]]

#print(output(uf))
result = [output(uf)]
for i in input_arr[::-1]:
    a = i[0]-1
    b = i[1]-1
    if not uf.same(a,b):
        x = uf.size[uf.root(a)] * uf.size[uf.root(b)]
        uf.unite(a,b)
        result.append(result[-1]-x)
    else:
        result.append(result[-1])

for i in result[::-1][1:]:
    print(i)

#print(uf.par)


### FIXED CODE ###

# UnionTreeクラス：グループ分けを木構造で管理する
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.root(self.par[x])

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]

n, m = (int(i) for i in input().split())
input_arr = [[int(i) for i in input().split()] for i in range(m)] 

uf = UnionFind(n)
#input_arr = [[1,2],[3,4],[1,3],[2,3],[1,4]]

#print(output(uf))
result = [int(n*(n-1)/2)]
for i in input_arr[::-1]:
    a = i[0]-1
    b = i[1]-1
    if not uf.same(a,b):
        x = uf.size[uf.root(a)] * uf.size[uf.root(b)]
        uf.unite(a,b)
        result.append(int(result[-1]-x))
    else:
        result.append(result[-1])

for i in result[::-1][1:]:
    print(i)

#print(uf.par)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N-1)]
px = [list(map(int,input().split())) for _ in range(Q)]

query = [[] for _ in range(N)]
ans = [[0] for _ in range(N)]

for p,x in px:
    query[p-1].append(x)
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(b-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    for q in query[v]:
        val += q
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
        
    
    
dfs(0,0)
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N-1)]
px = [list(map(int,input().split())) for _ in range(Q)]

query = [0] * N
ans = [0] * N

for p,x in px:
    query[p-1] = query[p-1] + x
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(b-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    val += query[v]
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
    return 
        
dfs(0,0)
print(*ans)
### BUGGY CODE ###

import itertools
n = int(input())
s = list(input())
a = ['0','1','2','3','4','5','6','7','8','9']
cnt=0
for i in list(itertools.product(a, repeat=3)):
  d =0
  e =0
  while d < n:
    if s[d] == i[e]:
      e+=1
    d+=1
    if e==3:
      cnt+=1
      break
print(cnt)

### FIXED CODE ###

n = int(input())
s = list(input())
a = ['0','1','2','3','4','5','6','7','8','9']
g = []
for i in a:
  for j in a:
    for k in a:
      g.append([i,j,k])
cnt=0
for i in g:
  d =0
  e =0
  while d < n:
    if s[d] == i[e]:
      e+=1
    d+=1
    if e==3:
      cnt+=1
      break
print(cnt)
### BUGGY CODE ###

import itertools
N=int(input())
L=list(map(int,input().split()))

p=itertools.combinations(L,3)

s=0
for i in p:
  if i[0]<i[1]+i[2] and i[1]<i[0]+i[2] and i[2]<i[1]+i[0]:
    s += 1

print(s)

### FIXED CODE ###

from bisect import bisect_left
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):#一番短い棒
  for j in range(i+1,n):#二番目に短い棒
    #1+2番目の棒の長さより短く、2番目に短い棒より長い棒の範囲を探す
    ans += bisect_left(l,l[i]+l[j])-(j+1)
print(ans)
### BUGGY CODE ###

from sys import stdin
import sys

A, B, N = [int(x) for x in stdin.readline().rstrip().split()]
# N, M = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
ans = int((A*N)/B)-A*int(N/B)
if N >= B:
    n = int(N/B)
    for i in range(n):
        x = i*B
        temp = ans1 = int((A*(x-1))/B)-A*int((x-1)/B)
        if temp > ans:
            ans = temp
    n = n*B
    ans1 = int((A*(n-1))/B)-A*int((n-1)/B)
    ans3 = int((A*(n+1))/B)-A*int((n+1)/B)
    ans2 = int((A*(B-1))/B)-A*int((B-1)/B)
    ans4 = int((A*(B+1))/B)-A*int((B+1)/B)
    ans5 = int((A*(n))/B)-A*int((n)/B)
else:
    ans1 = ans
    ans2 = ans
    ans3 = ans
    ans4 = ans
    ans5 = ans


print(max(ans, ans1, ans2, ans3, ans4, ans5))


### FIXED CODE ###

from sys import stdin
import sys

A, B, N = [int(x) for x in stdin.readline().rstrip().split()]
# N, M = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
x=min(B-1,N)
ans = int((A*x)/B)-A*int(x/B)
print(ans)
# if N >= B:
### BUGGY CODE ###

import numpy as np
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
p = np.array(p)

p_isorder = p[1:]>p[:-1]

ans = n - k + 1
no_change = False
for j in range(k-1):
    if not p_isorder[j]:
        break
else:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    for j in range(k-1):
        if not p_isorder[i+j+1]:
            break
    else:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

### FIXED CODE ###

import numpy as np
import heapq

(n,k),p = [list(map(int, s.split())) for s in open(0)]

p_np = np.array(p)
p_cumsum = (p_np[1:]>p_np[:-1]).cumsum()

c = [False] * n

_min = p[:k].copy()
_max = [-x for x in p[:k]]
heapq.heapify(_min)
heapq.heapify(_max)

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    decrease = False
    
    heapq.heappush(_min, p[i+k])
    heapq.heappush(_max, -p[i+k])
    
    while c[_min[0]]:
        heapq.heappop(_min)
    while c[-_max[0]]:
        heapq.heappop(_max)
    
    if (_min[0]==p[i] and -_max[0]==p[i+k]):
        ans -= 1
        decrease = True
    
    c[p[i]] = True
    
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not decrease:
            ans -= 1
        no_change = True

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

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

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

print(ans)

### FIXED CODE ###

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

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

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

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

ans = 0

for a in range(N):
    for b in range(a+1, N):
        for c in range(b+1, N):
            if L[a] < L[b] + L[c] and L[b] < L[c] + L[a] and L[c] < L[a] + L[b]:
                ans += 1

print(ans)


### FIXED CODE ###

# https://takeg.hatenadiary.jp/entry/2019/11/22/212816

import bisect

def solve():
    N = int(input())
    Ls = list(map(int, input().split()))
    Ls.sort()

    # O(N^2 * logN)の全探索で解く
    ans = 0
    for a_i in range(N):
        for b_i in range(a_i+1, N):
            c_i = bisect.bisect_left(Ls, Ls[a_i]+Ls[b_i])
            if c_i > b_i:
                ans += c_i - b_i - 1
            else:
                pass

    print(ans)

if __name__ == "__main__":
    solve()