Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from sys import *

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
last = arr[n - 1]
for i in range(n - 1, -1, -1):
	if arr[i] > last:
		d = arr[i] - last
		if d > 1:
			exit(print("No"))
	last = min(last, arr[i])
print("Yes")

Fixed submission:
from sys import *

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
last = arr[n - 1]
for i in range(n - 1, -1, -1):
	if arr[i] > last:
		d = arr[i] - last
		if d > 1:
			print("No")
			exit(0)
	last = min(last, arr[i])
print("Yes")

Buggy python submission (verdict: Runtime Error):
from sys import *

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
last = arr[n - 1]
for i in range(n - 1, 0, -1):
	if arr[i] > last:
		d = arr[i] - last
		if d > 1:
			exit(print("No"))
	last = min(last, arr[i])
print("Yes")

Fixed submission:
from sys import *

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
last = arr[n - 1]
for i in range(n - 1, -1, -1):
	if arr[i] > last:
		d = arr[i] - last
		if d > 1:
			print("No")
			exit(0)
	last = min(last, arr[i])
print("Yes")
Buggy python submission (verdict: Runtime Error):
s = input()
fre = [0] * 27
for ch in s:
  fre[ord(ch)] += 1
  if fre[ord(ch)] > 1:
    print("no")
    exit()
print("yes")

Fixed submission:
from sys import *

s = stdin.readline()
fre = [0] * 200
for ch in s:
	fre[ord(ch)] += 1
	if fre[ord(ch)] > 1:
		print("no")
		exit()
print("yes")
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate
MOD = 10 ** 9 + 7
S = int(input())

# dp[a][b]: 長さaで、合計bである数列の数

dp = [0] * (S+4)
dp[0] = 1
acc = list(accumulate(dp))
acc[-1] = acc[-2] = acc[-3] = 0

ans = 0
for a in range(700):
    ndp = []
    for b in range(S+1):
        ndp.append(acc[b-3] % MOD)
    ans += ndp[S]
    ans %= MOD
    dp = ndp
    acc = list(accumulate(dp))
    acc[-1] = acc[-2] = acc[-3] = 0

print(ans)


Fixed submission:
from itertools import accumulate
MOD = 10 ** 9 + 7
S = int(input())

# dp[a][b]: 長さaで、合計bである数列の数

dp = [0] * (S+4)
dp[0] = 1
acc = list(accumulate(dp))
acc[-1] = acc[-2] = acc[-3] = 0

ans = 0
for a in range(700):
    ndp = []
    for b in range(S+1):
        ndp.append(acc[b-3] % MOD)
    ndp += [0, 0, 0]
    ans += ndp[S]
    ans %= MOD
    dp = ndp
    acc = list(accumulate(dp))
    acc[-1] = acc[-2] = acc[-3] = 0

print(ans)
Buggy python submission (verdict: Runtime Error):
import math

def main():
    N = int(input())
    As = list(map(int, input().split()))
    pairwise_flag = True
    setwise_flag = True
    if N > 78498:
        pairwise_flag = False
    
    L = 1000 + 1
    isPrime = [True] * L
    isPrime[0] = isPrime[1] = False
    primes = []
    for n in range(2, L):
        if isPrime[n]:
            primes.append(n)
            isPrime[2*n::n] = [False] * ((L-n-1) // n)

    or_factor = 0
    or_factor_over1000 = set()
    all_gcd = None
    for i, a in enumerate(As):
        divs = set()
        digit = 1
        factor = 0
        x = a
        for k, p in enumerate(primes):
            if x % p == 0:
                factor += digit
                x //= p

            while x % p == 0:
                x //= p
            digit <<= 1

        if i > 0:
            all_gcd = math.gcd(all_gcd, a)
            if pairwise_flag:
                if or_factor & factor:
                    pairwise_flag = False
                or_factor |= factor
                if x > 1:
                    if x in or_factor_over1000:
                        pairwise_flag = False
                    or_factor_over1000.add(x)
        else:
            all_gcd = a
            if x > 1:
                common_factor_over1000.add(x)
    if pairwise_flag:
        print('pairwise coprime')
    elif all_gcd > 1:
        print('not coprime')
    else:
        print('setwise coprime')

main()


Fixed submission:
import math

def main():
    N = int(input())
    As = list(map(int, input().split()))
    pairwise_flag = True
    setwise_flag = True
    cnt_not1 = 0
    for a in As:
        if a > 1:
            cnt_not1 += 1
    if cnt_not1 > 78498:
        pairwise_flag = False
    
    L = 1000 + 1
    isPrime = [True] * L
    isPrime[0] = isPrime[1] = False
    primes = []
    for n in range(2, L):
        if isPrime[n]:
            primes.append(n)
            isPrime[2*n::n] = [False] * ((L-n-1) // n)

    or_factor = 0
    or_factor_over1000 = set()
    all_gcd = None
    for i, a in enumerate(As):
        digit = 1
        factor = 0
        x = a
        if pairwise_flag:
            for p in primes:
                if p > x:
                    break
                if x % p == 0:
                    factor += digit
                    x //= p

                while x % p == 0:
                    x //= p
                digit <<= 1

        if i > 0:
            all_gcd = math.gcd(all_gcd, a)
            if pairwise_flag:
                if or_factor & factor:
                    pairwise_flag = False
                or_factor |= factor
                if x > 1:
                    if x in or_factor_over1000:
                        pairwise_flag = False
                    or_factor_over1000.add(x)
        else:
            all_gcd = a
            or_factor |= factor
            if x > 1:
                or_factor_over1000.add(x)
    if pairwise_flag:
        print('pairwise coprime')
    elif all_gcd > 1:
        print('not coprime')
    else:
        print('setwise coprime')

main()
Buggy python submission (verdict: Runtime Error):
N = int(input())
X = input()

def popcount(n):
    return bin(n).count('1')

def process(n):
    return n % popcount(n)

def func(n):
    ret = 0
    while n > 0:
        n = process(n)
        ret += 1
    return ret

pcnt = X.count('1')
mods_plus = []
totalmod_plus = 0
tmp_plus = 1
pp = pcnt+1
mods_minus = []
totalmod_minus = 0
tmp_minus = 1
pm = pcnt-1
for c in reversed(X):
    if c == '1':
        totalmod_plus += tmp_plus
        totalmod_plus %= pp
    mods_plus.append(tmp_plus)
    tmp_plus = tmp_plus*2 % pp
    if pcnt > 0:
        if c == '1':
            totalmod_minus += tmp_minus
            totalmod_minus %= pm
        mods_minus.append(tmp_minus)
        tmp_minus = tmp_minus*2 % pm

for i in range(N):
    if X[i] == '1':
        if pcnt == 1:
            print(0)
        else:
            mod = mods_minus[-i-1]
            print(func((totalmod_minus - mod) % pm) + 1)
    else:
        mod = mods_plus[-i-1]
        print(func((totalmod_plus + mod) % pp) + 1)


Fixed submission:
N = int(input())
X = input()

def popcount(n):
    return bin(n).count('1')

def process(n):
    return n % popcount(n)

def func(n):
    ret = 0
    while n > 0:
        n = process(n)
        ret += 1
    return ret

pcnt = X.count('1')
mods_plus = []
totalmod_plus = 0
tmp_plus = 1
pp = pcnt+1
mods_minus = []
totalmod_minus = 0
tmp_minus = 1
pm = pcnt-1
for c in reversed(X):
    if c == '1':
        totalmod_plus += tmp_plus
        totalmod_plus %= pp
    mods_plus.append(tmp_plus)
    tmp_plus = tmp_plus*2 % pp
    if pcnt != 1:
        if c == '1':
            totalmod_minus += tmp_minus
            totalmod_minus %= pm
        mods_minus.append(tmp_minus)
        tmp_minus = tmp_minus*2 % pm

for i in range(N):
    if X[i] == '1':
        if pcnt == 1:
            print(0)
        else:
            mod = mods_minus[-i-1]
            print(func((totalmod_minus - mod) % pm) + 1)
    else:
        mod = mods_plus[-i-1]
        print(func((totalmod_plus + mod) % pp) + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

ans = 0
for i in range(1, N+1):
    first = i
    n = N // i
    last = n * i
    ans += (first + last) * n // 2
print(ans)


Fixed submission:
import math
N = int(input())

ans = 0
for i in range(1, N+1):
    first = i
    n = N // i
    last = n * i
    ans += (first + last) * n // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
N, K = map(int, input().split())
As = list(map(int, input().split()))

if K >= 40:
    print(' '.join(map(str, [N]*N)))
    exit()

for _ in range(K):
    events = [[] for _ in range(N*2+2)]
    for i, a in enumerate(As):
        l = 2*(i-a)-1
        r = 2*(i+a)+1
        events[-1 if l < -1 else l].append(i)
        events[N*2 if r > N*2 else r].append(i)
    active = set()
    L = 0
    nextAs = []
    for i in range(N):
        for k in events[2*i-1]:
            if k in active:
                active.remove(k)
                L -= 1
            else:
                active.add(k)
                L += 1
        nextAs.append(L)
    As = nextAs

print(' '.join(map(str, As)))


Fixed submission:
from bisect import bisect_left
N, K = map(int, input().split())
As = list(map(int, input().split()))

if K >= 40:
    print(' '.join(map(str, [N]*N)))
    exit()

for _ in range(K):
    events = [[] for _ in range(N*2+2)]
    for i, a in enumerate(As):
        l = 2*(i-a)-1
        r = 2*(i+a)+1
        events[-1 if l < -1 else l].append(i)
        events[N*2 if r > N*2 else r].append(i)
    active = [0] * N
    L = 0
    nextAs = [0] * N
    for i in range(N):
        for k in events[2*i-1]:
            if active[k]:
                active[k] = 0
                L -= 1
            else:
                active[k] = 1
                L += 1
        nextAs[i] = L
    As = nextAs

print(' '.join(map(str, As)))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from fractions import Fraction
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        f = Fraction(a, b)
        ct[f] += 1
ans = pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for f in ct.keys():
    if f in visited:
        continue
    inv = Fraction(-f.denominator, f.numerator)
    visited.add(f)
    visited.add(inv)
    tmp = pow(2, ct[f], MOD) + pow(2, ct[inv], MOD) - 1
    ans *= tmp
    ans %= MOD
ans += Allzero
print((ans-1) % MOD)


Fixed submission:
from collections import Counter
from fractions import Fraction
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        f = Fraction(a, b)
        ct[(f.numerator, f.denominator)] += 1
ans = pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for (a, b) in ct.keys():
    if (a, b) in visited:
        continue
    inv = Fraction(-b, a)
    ia, ib = inv.numerator, inv.denominator
    visited.add((a, b))
    visited.add((ia, ib))
    tmp = pow(2, ct[(a, b)], MOD) + pow(2, ct[(ia, ib)], MOD) - 1
    ans *= tmp
    ans %= MOD
ans += Allzero
print((ans-1) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from fractions import Fraction
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        f = Fraction(a, b)
        ct[f] += 1
ans = pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for f in ct.keys():
    if f in visited:
        continue
    inv = Fraction(-f.denominator, f.numerator)
    visited.add(f)
    visited.add(inv)
    tmp = pow(2, ct[f], MOD) + pow(2, ct[inv], MOD) - 1
    ans *= tmp
    ans %= MOD
ans += Allzero
print((ans-1) % MOD)


Fixed submission:
from collections import Counter
from fractions import Fraction
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        f = Fraction(a, b)
        ct[(f.numerator, f.denominator)] += 1
ans = pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for (a, b) in ct.keys():
    if (a, b) in visited:
        continue
    inv = Fraction(-b, a)
    ia, ib = inv.numerator, inv.denominator
    visited.add((a, b))
    visited.add((ia, ib))
    tmp = pow(2, ct[(a, b)], MOD) + pow(2, ct[(ia, ib)], MOD) - 1
    ans *= tmp
    ans %= MOD
ans += Allzero
print((ans-1) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: x[1])

dp = [[0] * (N+1) for _ in range(N+1)]
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        idx, a = arridx[i]
        lsc = rsc = 0
        if l > 0:
            # l-1, r から
            lsc = dp[l-1][r] + a * abs(l-1-idx)
        if r < N-1:
            # l, r+1 から
            rsc = dp[l][r+1] + a * abs(r+1-idx)
        dp[l][r] = max(lsc, rsc)
print(max(dp[i][i-1] for i in range(N)))

Fixed submission:
N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: x[1])

dp = {}
dp[(0, N-1)] = 0
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        idx, a = arridx[i]
        lsc = rsc = 0
        if l > 0:
            # l-1, r から
            lsc = dp[(l-1, r)] + a * abs(l-1-idx)
        if r < N-1:
            # l, r+1 から
            rsc = dp[(l, r+1)] + a * abs(r+1-idx)
        ndp[(l, r)] = max(lsc, rsc)
    dp = ndp
print(max(dp.values()))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: x[1])

dp = {}
dp[(0, N-1)] = 0
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        idx, a = arridx[i]
        lsc = rsc = 0
        if l > 0:
            # l-1, r から
            lsc = dp[(l-1, r)] + a * abs(l-1-idx)
        if r < N-1:
            # l, r+1 から
            rsc = dp[(l, r+1)] + a * abs(r+1-idx)
        ndp[(l, r)] = max(lsc, rsc)
    dp = ndp
print(max(dp.values()))

Fixed submission:
N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: x[1])

dp = {}
dp[(0, N-1)] = 0
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        idx, a = arridx[i]
        lsc = rsc = 0
        if l > 0:
            # l-1, r から
            lsc = dp[(l-1, r)] + a * abs(l-1-idx)
        if r < N-1:
            # l, r+1 から
            rsc = dp[(l, r+1)] + a * abs(r+1-idx)
        ndp[(l, r)] = max(lsc, rsc)
    dp = ndp
print(max(dp.values()))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N, P = map(int, input().split())
S = input()

ans = 0
if P in [2, 5]:
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
else:
    ct = Counter()
    ct[0] = 1
    for i in range(N-1, -1, -1):
        n = int(S[i:])
        mod = n % P
        ans += ct[mod]
        ct[mod] += 1
print(ans)

Fixed submission:
from collections import Counter
N, P = map(int, input().split())
S = input()

ans = 0
if P in [2, 5]:
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
else:
    ct = Counter()
    ct[0] = 1
    prevmod = 0
    mods = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in range(N-1, -1, -1):
        n = int(S[i])
        mod = (mods[n] + prevmod) % P
        ans += ct[mod]
        ct[mod] += 1
        prevmod = mod
        mods = [10 * a % P for a in mods]
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import Counter
N, P = map(int, input().split())
S = input()
L = len(str(P))
M = []
for i in range(10 ** (L+1)):
    M.append(i % P)

q = Counter([int(S[i:L-1]) for i in range(L-1)])
q[0] += 1
ans = 0
for i in range(L-1, N):
    nq = Counter()
    n = int(S[i])
    for a, c in q.items():
        s = M[a * 10 + n]
        if s == 0:
            ans += c
        nq[s] += c
    nq[0] += 1
    q = nq
print(ans)

Fixed submission:
from collections import Counter
N, P = map(int, input().split())
S = input()

ans = 0
if P in [2, 5]:
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
else:
    ct = Counter()
    ct[0] = 1
    prevmod = 0
    mods = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in range(N-1, -1, -1):
        n = int(S[i])
        mod = (mods[n] + prevmod) % P
        ans += ct[mod]
        ct[mod] += 1
        prevmod = mod
        mods = [10 * a % P for a in mods]
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import Counter
N, P = map(int, input().split())
S = input()
L = len(str(P))
M = []
for i in range(10 ** L):
    M.append(i % P)

q = Counter([int(S[i:L-1]) for i in range(L-1)])
q[0] += 1
ans = 0
for i in range(L-1, N):
    nq = Counter()
    n = int(S[i])
    for a, c in q.items():
        s = (a * 10 + n) % P
        if s == 0:
            ans += c
        nq[s] += c
    nq[0] += 1
    q = nq
print(ans)

Fixed submission:
from collections import Counter
N, P = map(int, input().split())
S = input()

ans = 0
if P in [2, 5]:
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
else:
    ct = Counter()
    ct[0] = 1
    prevmod = 0
    mods = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in range(N-1, -1, -1):
        n = int(S[i])
        mod = (mods[n] + prevmod) % P
        ans += ct[mod]
        ct[mod] += 1
        prevmod = mod
        mods = [10 * a % P for a in mods]
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
A, B = map(int, input().split())
print(A * B // math.gcd(A, B))

Fixed submission:
import fractions
A, B = map(int, input().split())
print(A * B // fractions.gcd(A, B))
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())                                                As = list(map(int, input().split()))
Fs = list(map(int, input().split()))                                                                                                                            As.sort()
As.reverse()                                                                    Fs.sort()
arr = []                                                                        M = 0
for a, f in zip(As, Fs):
    af = a*f                                                                        arr.append((af, a, f))                                                          M = af if af > M else M                                                     
f = -1                                                                          t = M                                                                           while f + 1 < t:
    m = f + (t-f) // 2
    k = K
    for AF, A, F in arr:                                                                d = A - m // F                                                                  if d > k:
            f = m
            break
        k -= d
    else:
        t = m

print(t)

Fixed submission:
import math
N, K = map(int, input().split())
As = list(map(int, input().split()))
Fs = list(map(int, input().split()))

As.sort()
As.reverse()
Fs.sort()
arr = []
M = 0
for a, f in zip(As, Fs):
    af = a*f
    arr.append((af, a, f))
    M = af if af > M else M

f = -1
t = M
while f + 1 < t:
    m = f + math.ceil((t-f) / 2)
    k = K
    for AF, A, F in arr:
        d = A - m // F
        d = d if d >= 0 else 0
        if d > k:
            f = m
            break
        k -= d
    else:
        t = m

print(t)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
# セグメント木(min, max)
N += 1
N0 = 2**(N-1).bit_length()
INF = float('inf')
minST = [INF]*(2*N0)
def update_min(k, x):
  k += N0-1
  minST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    minST[k] = min(minST[2*k+1], minST[2*k+2])
def query_min(l, r):
  L = l + N0; R = r + N0
  s = INF
  while L < R:
    if R & 1:
      R -= 1
      s = min(s, minST[R-1])
    if L & 1:
      s = min(s, minST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

MINF = float('-inf')
maxST = [MINF]*(2*N0)
def update_max(k, x):
  k += N0-1
  maxST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    maxST[k] = max(maxST[2*k+1], maxST[2*k+2])

def query_max(l, r):
  L = l + N0; R = r + N0
  s = MINF
  while L < R:
    if R & 1:
      R -= 1
      s = max(s, maxST[R-1])
    if L & 1:
      s = max(s, maxST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

Ps = list(map(int, input().split())) + [-1]
sorted_lens = []
tmp = 0
prev = -1
for i, p in enumerate(Ps):
  update_min(i, p)
  update_max(i, p)
  if prev > p:
    tmp = 0
  tmp += 1
  sorted_lens.append(tmp)
  prev = p

ans = N-K
flag = False
for i in range(N-K):
  smin = query_min(i, i+K+1)
  smax = query_max(i, i+K+1)
  if (smin == Ps[i] and smax == Ps[i+K]) or (flag and sorted_lens[i+K] >= K):
    ans -= 1
  if sorted_lens[i+K-1] == K:
    flag = True

print(ans)

Fixed submission:
N, K = map(int, input().split())
# セグメント木(min, max)
N += 1
N0 = 2**(N-1).bit_length()
INF = float('inf')
minST = [INF]*(2*N0)
def update_min(k, x):
  k += N0-1
  minST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    minST[k] = min(minST[2*k+1], minST[2*k+2])
def query_min(l, r):
  L = l + N0; R = r + N0
  s = INF
  while L < R:
    if R & 1:
      R -= 1
      s = min(s, minST[R-1])
    if L & 1:
      s = min(s, minST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

MINF = float('-inf')
maxST = [MINF]*(2*N0)
def update_max(k, x):
  k += N0-1
  maxST[k] = x
  while k >= 0:
    k = (k - 1) // 2
    maxST[k] = max(maxST[2*k+1], maxST[2*k+2])

def query_max(l, r):
  L = l + N0; R = r + N0
  s = MINF
  while L < R:
    if R & 1:
      R -= 1
      s = max(s, maxST[R-1])
    if L & 1:
      s = max(s, maxST[L-1])
      L += 1
    L >>= 1; R >>= 1
  return s

Ps = list(map(int, input().split())) + [-1]
sorted_lens = []
tmp = 0
prev = -1
for i, p in enumerate(Ps):
  update_min(i, p)
  update_max(i, p)
  if prev > p:
    tmp = 0
  tmp += 1
  sorted_lens.append(tmp)
  prev = p

ans = N-K
flag = False
for i in range(N-K):
  smin = query_min(i, i+K+1)
  smax = query_max(i, i+K+1)
  if (smin == Ps[i] and smax == Ps[i+K]) or (flag and sorted_lens[i+K] >= K):
    ans -= 1
  if sorted_lens[i+K-1] == K:
    flag = True

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
Ass = [list(map(int, input().split())) for _ in range(N)]
ct = Counter()
q = set([(i, 0) for i in range(N)])
idxs = [0] * N
n = 0
ans = 0
while q:
  nq = set()
  for i, k in q:
    a = i+1
    b = Ass[i][k]
    if a > b: a, b = b, a
    ct[(a, b)] += 1
    if ct[(a, b)] == 2:
      n += 1
      idxs[a-1] += 1
      if idxs[a-1] < N-1:
        nq.add((a-1, idxs[a-1]))
      idxs[b-1] += 1
      if idxs[b-1] < N-1:
        nq.add((b-1, idxs[b-1]))
  ans += 1
  q = nq
if n == N * (N-1) // 2:
  print(ans)
else:
  print(-1)

Fixed submission:
from collections import Counter
N = int(input())
Ass = [list(map(int, input().split())) for _ in range(N)]
ct = Counter()
q = set([(i, 0) for i in range(N)])
idxs = [0] * N
n = 0
ans = 0
while q:
  nq = set()
  for i, k in q:
    a = i+1
    b = Ass[i][k]
    if a > b: a, b = b, a
    ct[(a, b)] += 1
    if ct[(a, b)] == 2:
      n += 1
      idxs[a-1] += 1
      if idxs[a-1] < N-1:
        nq.add((a-1, idxs[a-1]))
      idxs[b-1] += 1
      if idxs[b-1] < N-1:
        nq.add((b-1, idxs[b-1]))
  ans += 1
  q = nq
if n == N * (N-1) // 2:
  print(ans)
else:
  print(-1)