Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def solve(ls, n, w):
	dp = [0] * (w + 1)
	for item in range(n):
		for weight in range(w, ls[item][0] - 1, -1):
			dp[weight] = max(dp[weight], dp[weight - ls[item][0]] + ls[item][1])
	return dp[w]


n, w = map(int, input().split())
ls = []
for i in range(n):
	ls.append(list(map(int, input().split())))

print(solve(ls, n, w))


Fixed submission:
n, w = map(int, input().split())
dp = [0] * (w + 1)
for j in range(n):
	w1, v1 = map(int, input().split())
	i = w
	while i >= 0 and i - w1 >= 0:
		dp[i] = max(dp[i - w1] + v1, dp[i])
		i -= 1
print(max(dp))
Buggy python submission (verdict: Runtime Error):
def calc(n):
    if n <= 1:
        return 1
    else:
        return 2 ** (n - 1)


def normailze(s, n):
    return (n - len(s)) * '0' + s


def solve(s):
    a = calc(len(s))
    cnt = 0
    n = len(s)
    for i in range(a):
        binary = normailze(bin(i)[2:], n - 1)
        b = s[0]
        f = 1
        for j in binary:
            if int(j) == 1:
                cnt += int(b)
                b = s[f]
                f += 1
            else:
                b += s[f]
                f += 1
        cnt += int(b)
    return cnt


print(solve(input()))


Fixed submission:
def calc(n):
    if n <= 1:
        return 1
    else:
        return 2 ** (n - 1)


def normailze(s, n):
    return (n - len(s)) * '0' + s


def solution(s):
    a = calc(len(s))
    cnt = 0
    n = len(s)
    if n ==1:
        return int(s)
    for i in range(a):
        binary = normailze(bin(i)[2:], n - 1)
        b = s[0]
        f = 1
        for j in binary:
            if int(j) == 1:
                cnt += int(b)
                b = s[f]
                f += 1
            else:
                b += s[f]
                f += 1
        cnt += int(b)
    return cnt

print(solution(input()))
Buggy python submission (verdict: Runtime Error):
n = int(input())
p = [int(input()) for _ in range(n)]
print(p.sum() - p.max()//2)

Fixed submission:
n = int(input())
p = [int(input()) for _ in range(n)]
print(sum(p) - max(p)//2)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

if m == 0:
    print(0)
else:
    ans = 0
    for i in range(8):
        a = []
        for z in x:
            r = 0
            for j in range(3):
                r += z[j] * (1 if i&2**j == 0 else -1)
            a.append(r)
        a.sort(reverse=True)
        ans = max(ans, sum(a[:m]))
print(ans)


Fixed submission:
n, m = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]

if m == 0:
    ans = 0
else:
    ans = 0
    for i in range(8):
        a = []
        for z in x:
            r = 0
            for j in range(3):
                r += z[j] * (1 if i&1<<j == 0 else -1)
            a.append(r)
        a.sort(reverse=True)
        ans = max(ans, sum(a[:m]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = [0]*n
b[0] = a[0]
for i in range(1, n):
    b[i] = b[i-1] ^ a[i]
    a[i] += a[i-1]

a.insert(0, 0)
b.insert(0, 0)

ans = 0
for i in range(0, n+1):
    for j in range(i+1, n+1):
        x = a[j]-a[i]
        y = b[j]^b[i]
        if x==y:
            ans += 1
print(ans)


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

ans = 0
p = 0
used = False
count = 1
for i in range(n):
    if a[i]^p == a[i]+p:
        if used:
            count += 1
        used = True
        p += a[i]
    else:
        c = count
        for j in range(i-c, i):
            count -= 1
            p -= a[j]
            if p^a[i] == p+a[i]:
                break
        if count == 0:
            p = a[i]
            count = 1
        else:
            count += 1
            p += a[i]
    ans += count
print(ans)
Buggy python submission (verdict: Runtime Error):
p=input
*x,=map(int, p().split())
print(sum(x)+max(x)*(2**int(p())-1))

Fixed submission:
a, b = map(int, input().split())
if a <= b:
    print(a)
else:
    print(a-1)

Buggy python submission (verdict: Runtime Error):
p=input
*x,=map(int, p().split())
print(sum(x)+max(x)*(2**int(p())-1))

Fixed submission:
a, b = map(int, input().split())
if a <= b:
    print(a)
else:
    print(a-1)
Buggy python submission (verdict: Runtime Error):
N = int(input())

if N == 3:
    print("2 3 25")
    exit()

MAX = 30000
v2, v3, v6 = [], [], []

for x in range(2, MAX+1):
    if x%6 == 0:
        v6.append(x)
    elif x%3 == 0:
        v3.append(x)
    elif x%2 == 0:
        v2.append(x)

ans = []
j = 0

while j < len(v2) and N > 3:
    ans.append(v2[j*2])
    ans.append(v2[j*2+1])
    j += 1
    N -= 2

j = 0
while j < len(v3) and N > 1:
    ans.append(v3[j*2])
    ans.append(v3[j*2+1])
    j += 1
    N -= 2

if N == 1:
    ans.append(6)

print(" ".join(map(str, ans)))

Fixed submission:
N = int(input())

if N == 3:
    print("2 5 63")
    exit()

MAX = 30000
v2, v3, v6 = [], [], []

for x in range(2, MAX+1):
    if x%6 == 0:
        v6.append(x)
    elif x%3 == 0:
        v3.append(x)
    elif x%2 == 0:
        v2.append(x)

ans = []
j = 0

while j < len(v2)//2 and N > 3:
    ans.append(v2[j*2])
    ans.append(v2[j*2+1])
    j += 1
    N -= 2

j = 0
while j < len(v3)//2 and N > 1:
    ans.append(v3[j*2])
    ans.append(v3[j*2+1])
    j += 1
    N -= 2

for j in range(N):
    ans.append(v6[j])


print(" ".join(map(str, ans)))
Buggy python submission (verdict: Runtime Error):
import numpy as np

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

# White : 1
# Black : 2

def count(field):


    return white, black

field = np.ones([100,100])

def print_():
    print("100 100")
    p = lambda x : "." if x == 1 else "#"
    for f in field:
        print("".join(list(map(p, f))))


A -= 1

x, y = 0, 0 #一つ飛ばしで黒にするところの座標
x_, y_ = 1, 0 #白がたりなくて埋めていくときの座標

while True:
    if A == 0 and B == 0:
        break

    if B > 0 and A > 0:
        if y == 0 or x == 0 or y == 99 or x == 99:
            field[y][x] = 2
            B -= 1
        else:
            field[y][x] = 2
            if field[y-1][x] == 1:
                A -= 1
                B -= 1
            else:
                pass
        x += 2
        if x >= 100:
            y += 1
            x = y%2

    elif B > 0:
        if y == 0 or x == 0 or y == 99 or x == 99:
            field[y][x] = 2
            B -= 1
        x += 2
        if x >= 100:
            y += 2
            x = 0

    elif A > 0:
        field[y_][x_] = 2
        if field[y_+1][x_] == 2 :
            A += 1
        count = 0
        for h, v in zip([0, 1], [1, 0]):
            if h+y_ < 0 or h+y_ >= 100 or v+x_ < 0 or v+x_ >= 100:
                continue
            if field[h+y_][v+x_] == 2:
                count += 1
        B += count
        x_ += 2
        if x_ >= 100:
            y_ += 1
            x_ = 1-y_%2

    else:
        print(A,B)
        raise
    print(A,B)


print_()

Fixed submission:
A = int(input())
B = int(input())
C = int(input())
D = int(input())

price = min(A, B) + min(C, D)
print(price)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

sum_even = sum(map(lambda i: A[i] if A[i] > 0 else 0, range(1, N, 2)))
sum_odd  = sum(map(lambda i: A[i] if A[i] > 0 else 0, range(0, N, 2)))

if sum_even == 0 and sum_odd == 0:
    max_ = max(A)
    print(max_)
    index = A.index(max_)
    print(len(A)-1)
    for _ in range(index):
        print(1)
    for j in range(N-index-1):
        print(N - index - j)
    exit()

print(max(sum_even, sum_odd))
EVEN = sum_even >= sum_odd
ans = []

if EVEN:
    A = A[1:]
    ans.append(1)
if len(A)%2 == 0:
    ans.append(len(A))
    A = A[:-1]

while len(A) > 1:
    if A[0] <= 0:
        ans.append(1)
        ans.append(1)
        A = A[2:]
    else:
        if A[2] <= 0:
            ans.append(3)
            A.pop(2)
            if len(A) == 2:
                ans.append(2)
                A.pop(1)
            else:
                ans.append(3)
                A.pop(2)
        else:
            ans.append(2)
            A.pop(1)
            A[0] += A.pop(1)
print(len(ans))
for a in ans:
    print(a)

Fixed submission:
N = int(input())

red = []
blue = []
count = 0

dellist = lambda items, indexes: [item for index, item in enumerate(items) if index not in indexes]

for n in range(2*N):
    v = list(map(int, input().split()))
    if n < N:
        red.append(v)
    else:
        blue.append(v)


for x in range(2*N):

    for k in range(2):
        r_remove_list = []
        b_remove_list = []

        for i, b in enumerate(blue):
            if b[k] == x:
                cand = -1
                max_ = -1
                max_j = -1
                for j, r in enumerate(red):
                    if r[k] < x:
                        if r[1-k] < b[1-k] and max_ < r[1-k]:
                            cand = j
                            max_ = r[1-k]
                            max_j = j
                if cand >= 0:
                    r_remove_list.append(max_j)
                    b_remove_list.append(i)

        blue = dellist(blue,b_remove_list)
        red = dellist(red,r_remove_list)
        count += len(b_remove_list)


print(count)
Buggy python submission (verdict: Runtime Error):
A,B = map(int, input().split())
S = list(input())
if A+B+1-S != 0:
    print("No")
    exit()
for i in range(len(S)):
    if (ord(S[i]) < ord("0") or ord(S[i]) > ord("9")) ^ i == A:
        print("No")
        exit()
print("Yes")


Fixed submission:
A,B = map(int, input().split())
S = list(input())
ans = len(S) == A+B+1 and S[A] == '-' and S.count('-') == 1
print(["No", "Yes"][ans])
Buggy python submission (verdict: Time Limit Exceeded):
Q = int(input())

def primes(n):
    p = [2]
    for i in range(3, n, 2):
        is_prime = True

        for p_ in p:
            if p_**2 > i:
                break
            if i%p_ == 0:
                is_prime = False
                break
        if is_prime:
            p.append(i)
    return p

primes = primes(10**5)

count_list = []
count = 0
for i in range(10**5//2):
    if 2*i+1 in primes:
        if (i+1) in primes:
            count += 1
    count_list.append(count)

def solve():
    l, r = list(map(int, input().split()))
    if l == 1:
        print(count_list[r//2])
    else:
        print(count_list[r//2] - count_list[l//2-1])

for q in range(Q):
    solve()

Fixed submission:
Q = int(input())

MAX = 10**5
is_primes = [True for _ in range(MAX+1)]
is_primes[0] = False
is_primes[1] = False

for i in range(2, MAX):
    if is_primes[i]:
        for j in range(2*i, MAX, i):
            is_primes[j] = False

count = 0
count_2017 = [0, 0]
for i in range(3, MAX, 2):
    if is_primes[i]:
        if is_primes[(i+1)//2]:
            count += 1
    count_2017.append(count)

for _ in range(Q):
    l, r = list(map(int, input().split()))
    print(count_2017[r//2+1] - count_2017[l//2])

Buggy python submission (verdict: Time Limit Exceeded):
Q = int(input())

def primes(n):
    p = [2]
    for i in range(3, n, 2):
        is_prime = True

        for p_ in p:
            if p_**2 > i:
                break
            if i%p_ == 0:
                is_prime = False
                break
        if is_prime:
            p.append(i)
    return p

primes = primes(10**5)

def solve():
    l, r = list(map(int, input().split()))

    count = 0
    for x in range(l, r+1, 2):
        if x in primes:
            if (x+1)/2 in primes:
                count += 1
    print(count)

for q in range(Q):
    solve()

Fixed submission:
Q = int(input())

MAX = 10**5
is_primes = [True for _ in range(MAX+1)]
is_primes[0] = False
is_primes[1] = False

for i in range(2, MAX):
    if is_primes[i]:
        for j in range(2*i, MAX, i):
            is_primes[j] = False

count = 0
count_2017 = [0, 0]
for i in range(3, MAX, 2):
    if is_primes[i]:
        if is_primes[(i+1)//2]:
            count += 1
    count_2017.append(count)

for _ in range(Q):
    l, r = list(map(int, input().split()))
    print(count_2017[r//2+1] - count_2017[l//2])
Buggy python submission (verdict: Runtime Error):

import math
X, Y = list(map(int, input().split()))
"""
print(math.ceil(math.log(Y/X+1, 2)))
"""
count = 0
while X <= Y:
    X *= 2
    count += 1
print(count)

Fixed submission:
a,b,c,d=map(int, input().split())
x = a+b-c-d
if x == 0:
    print("Balanced")
elif x > 0:
    print("Left")
else:
    print("Right")
Buggy python submission (verdict: Time Limit Exceeded):
s = list(map(len, input().split("T")))
*x, = map(int,input().split())
x[0] -= s[0]
s = s[1:]

ans = True
for j in range(2):
    dp = [False]*(8000*2+1)
    dp[8000] = True
    MAX, MIN = 8000, 8000
    for i in range(j, len(s), 2):
        dp_new = [False]*(8000*2+1)
        MIN_ = 8000*2+1
        MAX_ = -1
        for k in range(MIN, MAX+1):
            if dp[k]:
                dp_new[k-s[i]] = True
                MIN_ = min(MIN_, k-s[i])
                dp_new[k+s[i]] = True
                MAX_ = max(MAX_, k+s[i])
        dp = dp_new
        MIN, MAX = MIN_, MAX_
    ans = ans and dp[x[1-j]+8000]
print(["No","Yes"][ans])


Fixed submission:
s = list(map(len, input().split("T")))
*x, = map(int,input().split())
x[0] -= s[0]
s = s[1:]

moveX, moveY = [], []
for i in range(len(s)):
    if i%2 == 0:
        moveY.append(s[i])
    else:
        moveX.append(s[i])
X = [x[0]]
Y = [x[1]]
for x in moveX:
    X_ = []
    for cx in X:
        X_.append(cx+x)
        X_.append(cx-x)
    X = list(set(X_))
for y in moveY:
    Y_ = []
    for cy in Y:
        Y_.append(cy+y)
        Y_.append(cy-y)
    Y = list(set(Y_))
print(["No","Yes"][0 in X and 0 in Y])
Buggy python submission (verdict: Time Limit Exceeded):
n, c = map(int, input().split())
T = 10**5+1
l = [[0]*c for _ in range(T)]

for _ in range(n):
    s, t, c_ = map(int, input().split())
    c_ -= 1
    l[s-1][c_] += 1
    l[t][c_]   -= 1

for i in range(1, T):
    for c_ in range(c):
        l[i][c_] += l[i-1][c_]
        l[i-1][c_] = min(1, l[i-1][c_])

ans = 0
for i in range(T):
    ans = max(ans, sum(l[i]))

print(ans)


Fixed submission:
n, c = map(int, input().split())
T = 10**5+1
l = [[0]*c for _ in range(T)]

for _ in range(n):
    s, t, c_ = map(int, input().split())
    c_ -= 1
    for i in range(s-1, t):
        l[i][c_] = 1

ans = 0
for i in range(T):
    ans = max(ans, sum(l[i]))

print(ans)

Buggy python submission (verdict: Runtime Error):
l = [0]*(10**5+10)

n, c = map(int, input().split())
for _ in range(n):
    s, t, c = map(int, input().split())
    l[s*2-1] += 1
    l[t*2]   -= 1
for i in range(1, len(l)):
    l[i] += l[i-1]
print(max(l))


Fixed submission:
n, c = map(int, input().split())
T = 10**5+1
l = [[0]*c for _ in range(T)]

for _ in range(n):
    s, t, c_ = map(int, input().split())
    c_ -= 1
    for i in range(s-1, t):
        l[i][c_] = 1

ans = 0
for i in range(T):
    ans = max(ans, sum(l[i]))

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b, c = map(int,input().split())
    a -= 1
    b -= 1
    tree[a].append([b, c])
    tree[b].append([a, c])

q, k = map(int, input().split())
k -= 1
d = [0] * (n+1)

def dfs(x, c, p):
    global tree
    d[x] = c
    for leaf in tree[x]:
        if leaf[0] == p:
            continue
        else:
            dfs(leaf[0], leaf[1]+c, x)

dfs(k, 0, -1)
for i in range(q):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    print(d[a]+d[b])


Fixed submission:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b, c = map(int,input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

q, k = map(int, input().split())
d = [0] * (n+1)

def dfs(x, c, p):
    global tree
    d[x] = c
    for l, c_ in tree[x]:
        if l == p:
            continue
        else:
            dfs(l, c_+c, x)

dfs(k, 0, -1)
for i in range(q):
    a, b = map(int, input().split())
    print(d[a]+d[b])

Buggy python submission (verdict: Runtime Error):
n = int(input())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b, c = map(int,input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

q, k = map(int, input().split())

d = [0] * (n+1)

def dfs(x, c, p):
    global tree
    d[x] = c
    for leaf in tree[x]:
        if leaf[0] == p:
            continue
        else:
            dfs(leaf[0], leaf[1]+c, x)

dfs(k, 0, -1)
for i in range(q):
    a, b = map(int, input().split())
    print(d[a]+d[b])


Fixed submission:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
tree = [[] for _ in range(n+1)]

for _ in range(n-1):
    a, b, c = map(int,input().split())
    tree[a].append([b, c])
    tree[b].append([a, c])

q, k = map(int, input().split())
d = [0] * (n+1)

def dfs(x, c, p):
    global tree
    d[x] = c
    for l, c_ in tree[x]:
        if l == p:
            continue
        else:
            dfs(l, c_+c, x)

dfs(k, 0, -1)
for i in range(q):
    a, b = map(int, input().split())
    print(d[a]+d[b])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
ans = 1
max_count = 0
n = 2
while (n <= N):
  k = n
  count = 0
  while k%2 == 0:
    k /= 2
    count += 1
  if count > max_count:
    ans = n
    max_count = count
print(ans)

Fixed submission:
n = int(input())
ans = 1
while ans*2 <= n:
  ans *= 2
print(ans)
Buggy python submission (verdict: Runtime Error):
N, A, B = list(map(int, input().split()))
H = [int(input()) for _ in range(N)]

from math import ceil

def can_korosu(t):
    count = 0
    for h in H:
        count += ceil(max(0, h - t*B)/(A-B))
        if count > t:
            return False
    return True

lo = 0
hi = 10**9

p = (lo, hi)
for _ in range(50):
    mid = (hi + lo) // 2
    if can_korosu(mid):
        hi = mid
    else:
        lo = mid
    if p == (lo, hi):
        break
    p = (lo, hi)
print(hi)

Fixed submission:
a, b = map(int, input().split())
if a+b < 10:
    print(a+b)
else:
    print("error")
Buggy python submission (verdict: Time Limit Exceeded):
N, A, B = list(map(int, input().split()))
H = [int(input()) for _ in range(N)]

from math import ceil

def can_korosu(t):
    count = 0
    for h in H:
        count += ceil(max(0, h - t*B)/(A-B))
        if count > t:
            return False
    return True

lo = 0
hi = 10**9

for _ in range(50):
    mid = (hi + lo) // 2
    if can_korosu(mid):
        hi = mid
    else:
        lo = mid
print(hi)

Fixed submission:
N, A, B = list(map(int, input().split()))
H = [int(input()) for _ in range(N)]

from math import ceil

def can_korosu(t):
    count = 0
    for h in H:
        count += ceil(max(0, h - t*B)/(A-B))
        if count > t:
            return False
    return True

lo = 0
hi = 10**9

p = (lo, hi)
for _ in range(50):
    mid = (hi + lo) // 2
    if can_korosu(mid):
        hi = mid
    else:
        lo = mid
    if p == (lo, hi):
        break
    p = (lo, hi)
print(hi)
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int,input().split())
dp = [-1 for i in range(W+1)]
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(0, W-w+1):
        j = W-w-i
        if dp[j] >= 0:
            dp[j+w] = max(dp[j+w], dp[j]+v)
print(max(dp))


Fixed submission:
N, W = map(int,input().split())
V = [[] for _ in range(4)]

w, v = map(int,input().split())
w0 = w
V[0].append(v)

for _ in range(N-1):
    w, v = map(int,input().split())
    V[w-w0].append(v)
for i in range(4):
    V[i].sort(reverse=True)
    for j in range(1,len(V[i])):
        V[i][j] = V[i][j-1]+V[i][j]
    V[i].insert(0,0)
    V[i].append(0)

ans = 0
for i in range(len(V[0])):
    wi = w0*i
    if wi > W:
        break
    vi = V[0][i]
    for j in range(len(V[1])):
        wj = wi + (w0+1)*j
        if wj > W:
            break
        vj = vi + V[1][j]
        for k in range(len(V[2])):
            wk = wj + (w0+2)*k
            if wk > W:
                break
            vk = vj + V[2][k]

            l = min((W-wk)//(w0+3), len(V[3])-1)
            v = vk + V[3][l]
            ans = max(ans, v)
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
b = list(map(int, input().split()))
a = [b[0]]
for i in range(1, n):
    if a[-1] != b[i]:
        a.append(b[i])

ans = 1
inc = a[0] < a[1]

n = len(a)
i = 1
while i < n:
    if (a[i-1] < a[i]) ^ inc:
        ans += 1
        inc = a[i] < a[min(i+1, n-1)]
        i += 2
    else:
        i += 1
print(ans)

Fixed submission:
n = int(input())
b = list(map(int, input().split()))
a = [b[0]]
for i in range(1, n):
    if a[-1] != b[i]:
        a.append(b[i])

ans = 1
inc = a[0] < a[min(1, n-1)]

n = len(a)
i = 1
while i < n:
    if (a[i-1] < a[i]) ^ inc:
        ans += 1
        inc = a[i] < a[min(i+1, n-1)]
        i += 2
    else:
        i += 1
print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
b = list(map(int, input().split()))
a = [b[0]]
for i in range(1, n):
    if a[-1] != b[i]:
        a.append(b[i])

ans = 1
inc = a[0] < a[1]

n = len(a)
for i in range(1, n):
    if (a[i-1] > a[i]) ^ inc:
        pass
    else:
        ans += 1
        inc = not inc
print(ans)

Fixed submission:
n = int(input())
b = list(map(int, input().split()))
a = [b[0]]
for i in range(1, n):
    if a[-1] != b[i]:
        a.append(b[i])

ans = 1
inc = a[0] < a[min(1, n-1)]

n = len(a)
i = 1
while i < n:
    if (a[i-1] < a[i]) ^ inc:
        ans += 1
        inc = a[i] < a[min(i+1, n-1)]
        i += 2
    else:
        i += 1
print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)

ans = 0
for i in range(n):
    ans += a[2*i+1]

print(ans)

Fixed submission:
n = int(input())
b = list(map(int, input().split()))
a = [b[0]]
for i in range(1, n):
    if a[-1] != b[i]:
        a.append(b[i])

ans = 1
inc = a[0] < a[min(1, n-1)]

n = len(a)
i = 1
while i < n:
    if (a[i-1] < a[i]) ^ inc:
        ans += 1
        inc = a[i] < a[min(i+1, n-1)]
        i += 2
    else:
        i += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
n,a = map(int, input().split())
x = list(map(lambda x:int(x)-a, input().split()))
y = max(x)

dp = [[0]*(2*n*y+1) for _ in range(n+1)]
dp[0][n*y] = 1
for k in range(n):
    for i in range(2*n*y+1):
        if i+x[k] < 0 or i+x[k] > 2*n*y:
            dp[k+1][i] = dp[k][i]
        else:
            dp[k+1][i] = dp[k][i] + dp[k][i+x[k]]
print(dp[-1][n*y]-1)


Fixed submission:
n,a = map(int, input().split())
x = list(map(int, input().split()))
y = max(x)
x = [z-a for z in x]

dp = [[0]*(2*n*y+1) for _ in range(n+1)]
dp[0][n*y] = 1
for k in range(n):
    for i in range(2*n*y+1):
        res = dp[k][i]
        if i+x[k] < 0 or i+x[k] > 2*n*y:
            pass
        else:
            res += dp[k][i+x[k]]
        dp[k+1][i] = res
print(dp[-1][n*y]-1)
Buggy python submission (verdict: Runtime Error):
import numpy as np

MOD = 10 ** 9 +7

n,m = map(int,readline().split())
a = np.array(read().split(),np.int64)

a.sort()

def shake_cnt(x):
    X=np.searchsorted(a,x-a)
    return n*n-X.sum()

left = 0
right = 10 ** 6
while left+1 <right:
    x = (left + right)//2
    if shake_cnt(x) >= m:
        left = x
    else:
        right = x

left,right

X=np.searchsorted(a,right-a)
Acum = np.zeros(n+1,np.int64)
Acum[1:] = np.cumsum(a)

shake = n * n -X.sum()
happy = (Acum[-1]-Acum[X]).sum()+(a*(n-X)).sum()

happy += (m-shake)*left
print(happy)

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 +7

n,m = map(int,readline().split())
a = np.array(read().split(),np.int64)

a.sort()

def shake_cnt(x):
    X=np.searchsorted(a,x-a)
    return n*n-X.sum()

left = 0
right = 10 ** 6
while left+1 <right:
    x = (left + right)//2
    if shake_cnt(x) >= m:
        left = x
    else:
        right = x

left,right

X=np.searchsorted(a,right-a)
Acum = np.zeros(n+1,np.int64)
Acum[1:] = np.cumsum(a)

shake = n * n -X.sum()
happy = (Acum[-1]-Acum[X]).sum()+(a*(n-X)).sum()

happy += (m-shake)*left
print(happy)