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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Jun 12 12:37:02 2019

@author: YudNK
"""

N, Q = map(int, input().split())
X = []
P = []
for i in range(N):
    l = [int(j) for j in input().split()]
    X.append(l)
    X.sort()
for j in range(Q):
    P.append(int(input()))

result = [-1 for i in range(Q)]
for i in range(Q):
    for s in X:
        px = s[0] - P[i]
        for d in range(s[1] - s[0]):
            if px + d == s[2]:
                result[i] = px + d
        if result[i] != -1:
            break
[print(i) for i in result]

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    a = [s - x, t - x, x] #イベント
    E.append(a)
E.sort(key = lambda x: x[2])
D = []
for i in range(Q):
    D.append(int(input()))

ans = [-1]*Q
check = [-1]*Q

for e in E:
    l = bs.bisect_left(D, e[0])
    r = bs.bisect_left(D, e[1])
    while l < r:
        if check[l] == -1:  
            ans[l] = e[2]
            check[l] = r
            l += 1
        else:
            l = check[l]
        
[print(i) for i in ans]
### BUGGY CODE ###

N,K = map(int,input().split())
ps = list(map(int,input().split()))
su = 0
ind = 0
for i in range(N-K+1):
    ksum = sum(ps[i:i + K])
    if ksum > su:
        ind = i
        su = ksum
ki = 0

for i in range(ind, ind+K):
    ki += (ps[i]*(ps[i]+1))/2/ps[i]
print(ki)





### FIXED CODE ###

N,K = map(int,input().split())
ps = list(map(int,input().split()))
su = sum(ps[0:K])
ksum = su
ind = 0
for i in range(1,N-K+1):
    ksum -= ps[i-1]
    ksum += ps[i+K-1]
    if ksum > su:
        ind = i
        su = ksum
ki = 0

for i in range(ind, ind+K):
    ki += (ps[i]*(ps[i]+1))/2/ps[i]
print(ki)
### BUGGY CODE ###

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

# dp[i][j] = (s[i]で終わる部分文字列で、pで割ったあまりがjな数の個数)
dp = [[0] * p for _ in range(2)]

ans = 0
for i in range(n):
    i0, i1 = (i + 0) % 2, (i + 1) % 2
    dp[i1] = [0] * p
    for j in range(p):
        dp[i1][(j * 10 + int(s[i])) % p] += dp[i0][j]
    dp[i1][int(s[i]) % p] += 1

    ans += dp[i1][0]
    # print(dp[i1])

print(ans)


### FIXED CODE ###

from collections import defaultdict


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    ans = 1
    for i in range(1, k + 1):
        ans *= n - i + 1
        ans //= i
    return ans


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

if p == 2:
    ans = 0
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += i + 1
elif p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) in [0, 5]:
            ans += i + 1
else:
    mod_list = [0] * (n + 1)
    d = 1
    for i in reversed(range(n)):
        mod_list[i] = int(s[i]) * d + mod_list[i + 1]
        mod_list[i] %= p
        d = (d * 10) % p

    mod_dict = defaultdict(int)
    for i in range(n + 1):
        mod_dict[mod_list[i]] += 1

    # print(mod_list)
    # print(mod_dict)

    ans = 0
    for c in mod_dict:
        ans += comb(mod_dict[c], 2)

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

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

comb = 1
mod = 10**9+7
for i in range(min(K-2, N*M-K)):
    comb *= (N*M-2-i)
for i in range(min(K-2, N*M-K)):
    comb //= i+1
    
comb %= mod

x = (N*N*(N+1)//2-N*(N+1)*(2*N+1)//6)*M**2
y = (M*M*(M+1)//2-M*(M+1)*(2*M+1)//6)*N**2
ans = (x+y)*comb
print(ans%mod)

### FIXED CODE ###

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

mod = 10**9+7
a = 1
b = 1
for i in range(min(K-2, N*M-K)):
    a *= (N*M-2-i)
    a %= mod
    b *= i+1
    b %= mod
comb = a * pow(b, mod - 2, mod) % mod

ans = (((N*N*(N+1)//2-N*(N+1)*(2*N+1)//6)*M**2 + (M*M*(M+1)//2-M*(M+1)*(2*M+1)//6)*N**2)*comb)%mod
print(ans)
### BUGGY CODE ###

# def f(As, M):
#     prev = None
#     c = 0
#
#     for i, A in enumerate(As):
#         A %= M
#         if i == 0:
#             prev = {A: 1}
#             if A == 0:
#                 c += 1
#             continue
#
#         ccc = {A: 1}
#         for k in prev.keys():
#             v = prev[k]
#             newv = (k + A) % M
#             if newv in ccc:
#                 ccc[newv] += v
#             else:
#                 ccc[newv] = v
#         c += ccc[0] if 0 in ccc else 0
#         prev = ccc
#     return c
def f(As, M):
    totals = [As[0] % M]
    for A in As[1:]:
        totals.append((totals[-1] + A) % M)

    res = 0
    N = len(As)
    for i in range(N):
        ii = totals[N - 1 - i]
        if ii == 0:
            res += 1
        for j in range(i + 1, N):
            jj = totals[N - 1 - j]

            if jj == ii:
                res += 1
    return res


def main():
    N, M = [int(a) for a in input().split()]
    As = [int(a) for a in input().split()]
    print(f(As, M))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# def f(As, M):
#     prev = None
#     c = 0
#
#     for i, A in enumerate(As):
#         A %= M
#         if i == 0:
#             prev = {A: 1}
#             if A == 0:
#                 c += 1
#             continue
#
#         ccc = {A: 1}
#         for k in prev.keys():
#             v = prev[k]
#             newv = (k + A) % M
#             if newv in ccc:
#                 ccc[newv] += v
#             else:
#                 ccc[newv] = v
#         c += ccc[0] if 0 in ccc else 0
#         prev = ccc
#     return c
def f(As, M):
    totals = [As[0] % M]
    res = 1 if As[0] % M == 0 else 0
    for A in As[1:]:
        l = (totals[-1] + A) % M
        if l == 0:
            res += 1
        totals.append(l)

    # N = len(As)

    ddd = {}
    for t in totals:
        if t not in ddd:
            ddd[t] = 0
        res += ddd[t]
        ddd[t] += 1

    # for i in range(N):
    #     ii = totals[N - 1 - i]
    #     if ii == 0:
    #         res += 1
    #     for j in range(i + 1, N):
    #         jj = totals[N - 1 - j]
    #
    #         if jj == ii:
    #             res += 1
    return res


def main():
    N, M = [int(a) for a in input().split()]
    As = [int(a) for a in input().split()]
    print(f(As, M))


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

import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    P = W+1
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    L = 80*80*4
    mid = L//2
    dp = [[False]*(L+1) for _ in range((W+1)*(H+1))]
    for h in range(H+1):
        dp[h*P][mid] = True
    for w in range(H+1):
        dp[w][mid] = True
    
    for h in range(H):
        for w in range(W):
            c = A[h][w] - B[h][w]
            for l in range(L+1):
                if 0 <= l-c <= L:
                    dp[(h+1)*P+w+1][l] = dp[h*P+w+1][l-c] or dp[(h+1)*P+w][l-c]
                if 0 <= l+c <= L:
                    dp[(h+1)*P+w+1][l] = dp[(h+1)*P+w+1][l] or dp[h*P+w+1][l+c] or dp[(h+1)*P+w][l+c]
    ans = 10**9
    for l in range(L+1):
        if dp[H*P+W][l]:
            ans = min(abs(l-mid), ans)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    P = W+1
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    L = 80*80
    dp = [[False]*(L+1) for _ in range((W+1)*(H+1))]
    dp[P+1][abs(A[0][0]-B[0][0])] = True
    
    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0: continue
            c = abs(A[h][w] - B[h][w])
            for l in range(L-c+1):
                b1 = abs(l-c)
                b2 = abs(l+c)
                dp[(h+1)*P+w+1][l] = dp[h*P+w+1][b1] or dp[(h+1)*P+w][b1] or dp[h*P+w+1][b2] or dp[(h+1)*P+w][b2]

    for l in range(L+1):
        if dp[H*P+W][l]:
            print(l)
            break


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

from collections import defaultdict


def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out


def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import defaultdict


def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out


def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")

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

N, K = [ int(v) for v in input().split(" ") ]
points = [ int(v) for v in input().split(" ") ]
tmp = None

results = []

for i in range(K, N+1):
  next_score = 1
  if tmp == None:
    for p in points[i-K:i]:
      next_score *= p
  else:
    next_score = tmp / points[i-K-1] * points[i-1]
  tmp = next_score
  results.append(next_score)

#print(results)

for i in range(1, len(results)):
  if results[i] > results[i-1]:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N, K = [ int(v) for v in input().split(" ") ]
points = [ int(v) for v in input().split(" ") ]

for i in range(K+1, N+1):
  if points[i-K-1] < points[i-1]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

from operator import mul
from functools import reduce

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

for i in range(n-k):
    if reduce(mul,a[i:k+i]) < reduce(mul,a[i+1:k+i+1]):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(n-k):
    if a[i] < a[k+i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys, bisect

def main():
    _,M,*A = map(int, open(0).read().split())

    A.sort()
    for _ in range(M):
        a = int(A.pop() / 2)
        bisect.insort_left(A,a)

    print(sum(A))

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
from heapq import heappush, heappop

def main():
    _,M,*A = map(int, open(0).read().split())

    A = [-x for x in A] # reverse max to min
    A.sort()

    for _ in range(M):
        a = int(heappop(A) / 2)
        heappush(A, a)
    print(-sum(A))

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

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    num=max(a)
    a.remove(num)
    a.append(num//2)
print(sum(a))


### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=list(map(lambda x: x*(-1), a))
heapq.heapify(a)
for i in range(m):
    heapq.heappush(a, -1*(-heapq.heappop(a)//2))
print(sum(a)*-1)
### BUGGY CODE ###


ord_a = ord('a')

S = list(map(lambda c: ord(c)-ord_a,input()))
L = 26

memo = []

f = [0]*L
cnt = 0

for i,s in zip(reversed(range(len(S))),reversed(S)):

  cnt += (f[s] == 0)
  f[s] += 1
  if cnt == L:
    memo.append((i,f))
    f = [0]*L
    cnt = 0

memo.append((0,f))
result = []

for i,f in reversed(memo):
  if result:
    c = result[-1]
    for s in S[i:]:
      f[s] -= 1
      if s == c:
        break

  result.append(f.index(0))


print(''.join(map(lambda x: chr(x+ord_a), result)))

### FIXED CODE ###


ord_a = ord('a')
L = 26

S = list(map(lambda c: ord(c)-ord_a,input()))


memo = []

f = [0]*L
cnt = 0


for i,s in zip(reversed(range(len(S))),reversed(S)):

  cnt += (f[s] == 0)
  f[s] += 1
  if cnt == L:
    memo.append((i,f))
    f = [0]*L
    cnt = 0


result = [f.index(0)]

for i,f in reversed(memo):
  c = result[-1]
  for j in range(i,len(S)):
    s = S[j]
    f[s] -= 1
    if s == c:
      break

  result.append(f.index(0))

print(''.join(map(lambda x: chr(x+ord_a), result)))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
A = []
for _ in range(M):
    a = int(input())
    A.append(a)

dp = []
for i in range(N + 1):
    dp.append(None)
dp.append(0)

dp[N] = 1

for i in range(N - 1, -1, -1):
    if i in A:
        dp[i] = 0
        continue
    dp[i] = dp[i + 1] + dp[i + 2]

# print('dp', dp)
print(dp[0] % 1000000007)


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    # print(ANS)
    # if x in A:
    #     print('::::', x)
    #     d[x] = 0
    #     return 0
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2

    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, M, L = map(int, input().split())
    edges = [[] for _ in range(N)]

    for _ in range(M):
        fr, to, cost = map(int, input().split())
        fr -= 1
        to -= 1
        edges[fr].append((to, cost))
        edges[to].append((fr, cost))

    Q = int(input())
    ans = []
    for _ in range(Q):
        start, end = map(int, input().split())
        start -= 1
        end -= 1

        que = [(0, start, L, 0)]
        cntList = [INF] * N
        while que:
            cnt, now, fuel, var = heappop(que)

            if cntList[now] <= cnt:
                continue

            cntList[now] = cnt

            for to, cost in edges[now]:
                c = cnt
                f = fuel
                v = var
                if f - cost < 0:
                    if v == 0:
                        continue
                    c += 1
                    f = L
                    v -= 1
                heappush(que, (c, to, f - cost, v + 1))

        if cntList[end] == INF:
            ans.append(-1)
        else:
            ans.append(cntList[end])

    print(*ans, sep='\n')

sol()

### FIXED CODE ###

import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)
### BUGGY CODE ###

import re


n, q = map(int, input().split())
s = input()
ql = set(range(q))
for i in ql:
    ans = 0
    l1, l2 = map(int, input().split())
    s_part = s[l1 - 1:l2]
    s_re = re.findall(r'(AC)', s_part)
    for j in s_re:
        if j == 'AC':
            ans += 1
    else:
        print(ans)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
t = [0] * (n + 1)
nl = set(range(n))
for i in nl:
    t[i + 1] = t[i] + (1 if s[i:i + 2] == 'AC' else 0)
ql = set(range(q))
for i in ql:
    l1, l2 = map(int, input().split())
    ans = t[l2-1] - t[l1-1]
    print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    db = [a]
    cnt = k.bit_length()
    for c in range(1, cnt):
        temp = []
        for i in range(n):
            temp.append(db[c-1][db[c-1][i]-1])
        db.append(temp)

    res = 1
    for i in range(cnt):
        if (k>>i) & 1:
            res = db[i][res-1]
    print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#0や1のケースに注意
#index out of range

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    tugi = [0]*n
    tugi[0] = 1
    s = 0
    cnt = 1
    while 1:
        s = a[s] - 1
        cnt += 1
        if tugi[s] > 0:
            break
        tugi[s] = cnt
    cnt -= 1
    if cnt-1 >= k:
        for i in range(n):
            if tugi[i]==k+1:
                print(i+1)
    else:
        #s=ループスタート
        loop = [s]
        for i in range(cnt - (tugi[s]-1)-1):
            s = a[s] - 1
            loop.append(s)
        s = a[s]-1
        amari = (k-(tugi[s]-1)) % (len(loop))
        print(loop[amari]+1)

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


def solve():
    ans = "Yes"
    for i in range(1,N):
        tmp = min(H[i:])
        if H[i-1] - tmp > 1:
            ans = "No" 
            break
    print(ans)

if __name__ == "__main__":
    N = int(input())
    H = list(map(int, input().split()))  
    solve()


### FIXED CODE ###


def solve():
    ans = "Yes"
    for i in range(1,N-1):
        if H[i] > H[i+1]:
            H[i] -= 1
            if H[i] > H[i+1]:
                ans = "No"
                break
            if H[i-1] > H[i]:
                ans = "No"
                break
        elif H[i-1] <= H[i]-1:
            H[i] -= 1
    print(ans)

if __name__ == "__main__":
    N = int(input())
    H = list(map(int, input().split()))  
    solve()
### BUGGY CODE ###

import copy


def solve(n, tbl):
    use = copy.deepcopy(tbl)
    for k in range(n):
        for i in range(n):
            if i == k:
                continue
            for j in range(i + 1, n):
                if j == k:
                    continue
                ij, ik, kj = tbl[i][j], tbl[i][k], tbl[k][j]
                if ij > ik + kj:
                    return -1
                if ij == ik + kj:
                    use[i][j] = 0
    ans = 0
    for i, row in enumerate(use):
        ans += sum(row[i + 1:])

    return sum(sum(row[i + 1:]) for i, row in enumerate(use))


n = int(input())
tbl = [list(map(int, input().split())) for _ in range(n)]
print(solve(n, tbl))


### FIXED CODE ###

def solve(n, tbl):
    ans = 0
    for i, row_i in enumerate(tbl):
        for j in range(i + 1, n):
            row_j = tbl[j]
            ij = row_i[j]
            mind = min((ik + kj for ik, kj in zip(row_i, row_j) if ik and kj), default=float('inf'))
            if ij > mind:
                return -1
            if ij < mind:
                ans += ij
    return ans


n = int(input())
tbl = [list(map(int, input().split())) for _ in range(n)]
print(solve(n, tbl))
### BUGGY CODE ###

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

a.sort()
amax=a[-1]
amin=a[0]

dn=0
for i in range(amin,amax+1):
    ni=a.count(i)
    if ni>i:
        dn=dn+(ni-i)
    elif ni<i:
        dn=dn+ni

print(dn)        


### FIXED CODE ###

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

a.sort()
amax=a[-1]
amin=a[0]

s=[]
ai=a[0]
acnt=-1
for i in range(n):
    if a[i]>ai:
        s.append([ai,acnt+1])
        acnt=0
        ai=a[i]
    else:
        acnt=acnt+1
s.append([ai,acnt+1])
        
# print(s)
    
dn=0
for i in range(len(s)):
    ni=s[i][1]
    if ni>s[i][0]:
        dn=dn+(ni-s[i][0])
    elif ni<s[i][0]:
        dn=dn+ni

print(dn)
### BUGGY CODE ###

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

p_ordered = np.array([False]*(n-1))
for i in range(n-1):
    if p[i] < p[i+1]:
        p_ordered[i]=True

ans = n - k + 1
no_change = False
if p_ordered[:k-1].all():
    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
    
    if p_ordered[i+1:i+k].all():
        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())
print(0, flush=True)
s_st = input()
i_st = 0
if s=='Vacant': exit()
print(n-1, flush=True)
s_en = input()
i_en = n-1
if s=='Vacant': exit()
for _ in range(20)
    print((i_st+i_en)//2, flush=True)
    s_md = input()
    if s_md=='Vacant': exit()
    if (n-1)//2%2==0 and s_st!=s_md:
        i_en = (i_st+i_en)//2
    else:
        i_st = (i_st+i_en)//2
        s_st = s_md

### FIXED CODE ###

import sys
def valid():
    s = input()
    if s=='Vacant':
        sys.exit()
    return 1 if s=='Male' else 0

n = int(input())
print(0, flush=True)
s_l = valid()
lidx = 0
ridx = n

while True:
    midx = (lidx+ridx)//2
    print(midx, flush=True)
    s_m = valid()
    if ((midx-lidx)%2==1) ^ (s_l==s_m):
        lidx = midx
        s_l = s_m
    else:
        ridx = midx
### BUGGY CODE ###

a,b,n = map(int,input().split())
ma = 0

if(n<b):
    ma = (a*n)//b - (a* (n//b))
else:
    ma = (a*(b-1))//b - (a*((b-1)//b))
    for x in range(b,n+1):
        num = (a*x)//b - (a*(x//b))
        if(ma < num):
            ma = num

print(ma)

### FIXED CODE ###

a,b,n = map(int,input().split())
ma = 0

if(n<b):
    ma = (a*n)//b - (a* (n//b))
else:
    ma = (a*(b-1))//b - (a*((b-1)//b))
    """
    for x in range(b,n+1):
        
        num = (a*x)//b - (a*(x//b))
        if(ma > num):
            break
        ma = num
    """

print(ma)