Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p02850 (python)

Fixed submission:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**8)

N = int(input())
graph = [[] for _ in range(N)]
numOfEdges = [0 for _ in range(N)]
visited = [0 for _ in range(N)]
edges = defaultdict(int)

for i in range(1, N):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    numOfEdges[a] += 1
    numOfEdges[b] += 1
    edges[(a, b)] = 0
    graph[a].append(b)
    graph[b].append(a)

def dfs(prev, now, col):
    if visited[now]:
        return
    visited[now] = 1
    i = 1
    for adj in graph[now]:
        if adj == prev:
            continue
        if now < adj:
            edges[(now, adj)] = col + i
        else:
            edges[(adj, now)] = col + i
        dfs(now, adj, col+i)
        i += 1

dfs(-1, 0, 1)
maxColor = max(numOfEdges)
print(maxColor)

for k, i in edges.items():
    e = i % maxColor
    if e:
        print(e)
    else:
        print(maxColor)

Buggy submission (verdict: Runtime Error):
N = int(input())
graph = [[] for _ in range(N)]
numOfEdges = [0 for _ in range(N)]
visited = [0 for _ in range(N)]
edges = []

for i in range(1, N):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    edges.append((a, b))
    graph[a].append(b)
    graph[b].append(a)

def dfs(prev, now):
    if visited[now]:
        return
    visited[now] = 1
    numOfEdges[now] = len(graph[now])
    for adj in graph[now]:
        if adj == prev:
            continue
        dfs(now, adj)

dfs(-1, 0)
maxColor = max(numOfEdges)
print(maxColor)

for e in edges:
    a, b = e
    x, y = numOfEdges[a], numOfEdges[b]

    print(max(x, y))

    if x > y:
        numOfEdges[a] -= 1
    elif y > x:
        numOfEdges[b] -= 1
    else:
        numOfEdges[a] -= 1
        numOfEdges[b] -= 1
Problem p02921 (python)

Fixed submission:
S = input()
T = input()

ans = 0
for i in range(3):
    if S[i] == T[i]:
        ans += 1
print(ans)

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

ans = N * (N-1) / 2

print(int(ans))
Problem p02936 (python)

Fixed submission:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
#累積和を木に拡張する
N, Q = map(int, input().split())

graph = [[] for i in range(N)]
score = [0 for _ in range(N)]

def dfs(now, prev):

    for adj in graph[now]:
        if adj == prev:
            continue
        score[adj] += score[now]
        dfs(adj, now)

    return

for i in range(1, N):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

query = [0] * N
for i in range(Q):
    p, x = map(int, input().split())

    score[p-1] += x

dfs(0, -1)

for p in score:
    print(p)

Buggy submission (verdict: Runtime Error):
from collections import deque
#累積和を木に拡張する
N, Q = map(int, input().split())

graph = [[] for i in range(N)]
score = [0 for _ in range(N)]

def dfs(now, prev):

    for adj in graph[now]:
        if adj == prev:
            continue
        score[adj] += score[now]
        dfs(adj, now)

    return

for i in range(1, N):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

query = [0] * N
for i in range(Q):
    p, x = map(int, input().split())

    score[p-1] += x

dfs(0, -1)

for p in score:
    print(p)

Buggy submission (verdict: Runtime Error):
from collections import deque
N, Q = map(int, input().split())

graph = [[] for i in range(N)]

score = [0 for _ in range(N)]

def dfs(now, prev, addVal, visited):
    if graph[now] == prev:
        score[now]+= addVal
        return

    score[now] += addVal

    for adj in graph[now]:
        if adj < now:
            continue
        if adj == prev:
            continue
        if visited[adj]:
            continue
        visited[adj] = True

        dfs(adj, now, addVal, visited)


for i in range(1, N):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

for i in range(Q):
    p, x = map(int, input().split())

    visited = [False for _ in range(N)]
    dfs(p-1, -1, x, visited)

for i in range(N):
    print(score[i])
Problem p03043 (python)

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

ans = 0
for i in range(1, K):
    if i > N:
        break
    x = math.ceil(math.log2(K/i))
    p = (1/2)**x
    ans += p

ans *= 1/N

if N >= K:
    ans += (N-K+1)/N

print("{:.10f}".format(ans))

Buggy submission (verdict: Runtime Error):
import numpy as np
N, K = map(int, input().split())

ans = 0
for i in range(1, K):
    if i > N:
        break
    x = np.ceil(np.log2(K/i))
    p = (1/2)**x
    ans += p

ans *= 1/N

if N >= K:
    ans += (N-K+1)/N

print("{:.10f}".format(ans))
Problem p03436 (python)

Fixed submission:
from collections import deque
import sys
H, W = list(map(int, input().split()))

city = []

for _ in range(H):
    city.append(list(input()))

dist = [[float("inf") for _ in range(W)] for _ in range(H)]

dist_count = [0 for _ in range(H*W)]

queue = deque()
queue.append((0, 0))
dist[0][0] = 0

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

while len(queue) > 0:
    now_x, now_y = queue.popleft()

    for dx_, dy_ in zip(dx, dy):

        adj_x = now_x + dx_
        adj_y = now_y + dy_

        if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
            continue

        if city[adj_y][adj_x] == "#":
            continue

        if dist[adj_y][adj_x] > H*W:
            dist[adj_y][adj_x] = dist[now_y][now_x] + 1
            queue.append((adj_x, adj_y))
            dist_count[dist[adj_y][adj_x]] += 1

#すぬけ君がどうやってもたどり着けない場合
if dist[H-1][W-1] > H**W:
    print(-1)
    sys.exit()

#すぬけ君がたどり着ける場合
route_grids = dist[H-1][W-1] + 1

white_all = 0
for i in range(H):
    for j in range(W):
        if city[i][j] == ".":
            white_all += 1
ans = white_all - route_grids
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque
import sys
H, W = list(map(int, input().split()))

city = []

for _ in range(H):
    city.append(list(input()))

dist = [[float("inf") for _ in range(W)] for _ in range(H)]

dist_count = [0 for _ in range(H*W)]

queue = deque()
queue.append((0, 0))

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

while len(queue) > 0:
    now_x, now_y = queue.popleft()

    for dx_, dy_ in zip(dx, dy):

        adj_x = now_x + dx_
        adj_y = now_y + dy_

        if (not 0 <= adj_x < W) or (not 0 <= adj_y < H):
            continue

        if city[adj_y][adj_x] == "#":
            continue

        if dist[adj_y][adj_x] > H*W:
            dist[adj_y][adj_x] = dist[now_x][now_y] + 1
            queue.append((adj_x, adj_y))
            dist_count[dist[adj_y][adj_x]] += 1

#すぬけ君がどうやってもたどり着けない場合
if dist[H-1][W-1] > H*W:
    print(-1)
    sys.exit()

#すぬけ君がたどり着ける場合
max_dist = dist[H-1][W-1]

ans = 0
for i in range(1, max_dist+1):
    ans += dist[i] - 1
print(ans)
Problem p03579 (python)

Fixed submission:
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    graph[a].append(b)
    graph[b].append(a)


visited = [False for _ in range(N)]
color = [0 for _ in range(N)]

def dfs(now, c):

    color[now] = c

    for adj in graph[now]:
        if color[adj] == c:
            return False

        if color[adj] == 0 and not dfs(adj, -c):
            return False

    return True

ans = dfs(0, 1)
white = color.count(-1)
black = N - white
if ans:
    print(black * white - M)
else:
    print(N * (N-1)//2 - M)

Buggy submission (verdict: Runtime Error):
from collections import deque, defaultdict
N, M = map(int, input().split())
graph = [[] for _ in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    graph[a].append(b)
    graph[b].append(a)


visited = [False for _ in range(N)]
color = [0 for _ in range(N)]

def dfs(now, c):

    color[now] = c

    for adj in graph[now]:
        if color[adj] == c:
            return False

        if color[adj] == 0 and not dfs(adj, -c):
            return False

    return True

ans = dfs(0, 1)
white = color.count(-1)
black = N - white
if ans:
    print(black * white - M)
else:
    print(N * (N+1)//2 - M)
Problem p02609 (python)

Fixed submission:
# わからんわからんわからんわからんわからん
# なんで1500人も解いてんの？この界隈天才しかおらん
table = [0 for i in range(2*10**5+5)]
for i in range(2*10**5+5):
    table[i] = "{:0b}".format(i).count("1")


def main():
    N = int(input())
    X = input()
    t = X.count("1")
    x1, x2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            # 反転してt+1
            p = pow(2, N-i-1, t+1)
            x = x1 + p
            x %= t+1
        elif t != 1:
            p = pow(2, N-i-1, t-1)
            x = x2 - p
            x %= (t-1)
        else:
            ans = 0
        while x > 0:
            x %= table[x]
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# TLEするはず
def main():
    N = int(input())
    X = input()
    t = X.count("1")
    d1 = []
    d2 = []
    d11 = 1
    d22 = 1
    for i in range(1, N+1):
        d1.append(d11)
        d11 *= 2
        d11 %= t-1
        d2.append(d22)
        d22 *= 2
        d22 %= t+1
    V = int(X, 2)
    for i in range(N):
        x = 0
        cur_bits = 0
        if t != 1 and X[i] == "1":
            cur_bits = t - 1
            x = V ^ d1[N-i-1]
        elif t != 1:
            cur_bits = t + 1
            x = V ^ d2[N-i-1]
        else:
            x = 0
        ans = 0
        while x > 0:
            x = x % cur_bits
            ans += 1
            cur_bits = "{:0b}".format(x).count("1")
        print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# TLEするはず
def main():
    N = int(input())
    X = input()
    t = X.count("1")
    d1 = []
    d2 = []
    d11 = 1
    d22 = 1
    for i in range(1, N+1):
        d1.append(d11)
        d11 *= 2
        d11 %= t-1
        d2.append(d22)
        d22 *= 2
        d22 %= t+1
    V = int(X, 2)
    for i in range(N):
        x = 0
        cur_bits = 0
        if t != 1 and X[i] == "1":
            cur_bits = t - 1
            x = V ^ d1[N-i-1]
        elif t != 1:
            cur_bits = t + 1
            x = V ^ d2[N-i-1]
        else:
            x = 0
        ans = 0
        while x > 0:
            x = x % cur_bits
            ans += 1
            cur_bits = 0
            T = "{:0b}".format(x)
            for t in T:
                if t == "1":
                    cur_bits += 1
        print(ans)


if __name__ == '__main__':
    main()
Problem p02618 (python)

Fixed submission:
from random import randint
import sys
input = sys.stdin.readline


def main(D, C, S):
    for _ in range(D):
        print(randint(1, 26))


if __name__ == '__main__':
    D = int(input())
    C = [int(i) for i in input().split()]
    S = [[int(i) for i in input().split()] for j in range(D)]
    main(D, C, S)

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys
input = sys.stdin.readline
INF = 9223372036854775808


def calc_score(D, C, S, T):
    """
    開催日程Tを受け取ってそこまでのスコアを返す
    コンテストi 0-indexed
    d 0-indexed
    """
    score = 0
    last = [0]*26  # コンテストiを前回開催した日
    for d, t in enumerate(T):
        last[t] = d + 1
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
        score += S[d][t]
    return score


def evaluate(D, C, S, T, k):
    """
    d日目終了時点での満足度を計算し，
    d + k日目終了時点での満足度の減少も考慮する
    """
    score = 0
    last = [0]*26
    for d, t in enumerate(T):
        last[t] = d + 1
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
        score += S[d][t]

    for d in range(len(T), min(len(T) + k, D)):
        for i in range(26):
            score -= (d + 1 - last[i]) * C[i]
    return score


def update_score(D, C, S, T, score, ct, ci):
    """
    ct日目のコンテストをコンテストciに変更する
    スコアを差分更新する

    ct: change t 変更日 0-indexed
    ci: change i 変更コンテスト 0-indexed
    """
    last = [0]*26  # コンテストiを前回開催した日
    for d in range(ct):
        last[T[d]] = d + 1
    prei = T[ct]  # 変更前に開催する予定だったコンテストi
    score -= S[ct][prei]
    score += S[ct][ci]
    for d in range(ct, D):
        if d != ct and T[d] == prei:
            break
        score += C[prei]*(d + 1 - ct - 1)
        score -= C[prei]*(d + 1 - last[prei])
    for d in range(ct, D):
        if d != ct and T[d] == ci:
            break
        score += C[ci]*(d + 1 - last[ci])
        score -= C[ci]*(d + 1 - ct - 1)
    T[ct] = ci
    return score, T


def greedy(D, C, S):
    Ts = []
    for k in range(9, 14):
        T = []  # 0-indexed
        max_score = -INF
        for d in range(D):
            # d+k日目終了時点で満足度が一番高くなるようなコンテストiを開催する
            best_i = 0
            for i in range(26):
                T.append(i)
                score = evaluate(D, C, S, T, k)
                if max_score < score:
                    max_score = score
                    best_i = i
                T.pop()
            T.append(best_i)
        Ts.append((max_score, T))
    res = max(Ts, key=lambda pair: pair[0])[1]
    return res


if __name__ == '__main__':
    D = int(input())
    C = np.array([int(i) for i in input().split()])
    S = np.array([[int(i) for i in input().split()] for j in range(D)])
    T = greedy(D, C, S)
    for t in T:
        print(t+1)
Problem p02632 (python)

Fixed submission:
MOD = 10**9 + 7


def main():
    K = int(input())
    S = input()
    N = len(S)
    m = N+K + 5
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                fac[i] = fac[i-1] * i % MOD
                inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
                finv[i] = finv[i - 1] * inv[i] % MOD

    def COMB(n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

    COMBinitialize(m)
    ans = 0
    for i in range(K+1):
        v = COMB(N-1+K-i, N-1)
        v %= MOD
        v *= pow(25, (K-i), MOD)
        v %= MOD
        v *= pow(26, i, MOD)
        v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
https://kkt89.hatenablog.com/entry/2020/06/21/ABC171_F-Strivore

Buggy submission (verdict: Runtime Error):
MOD = 10**9 + 7
m = 10**6 + 5
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD


def COMB(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


def main():
    K = int(input())
    S = input()
    N = len(S)
    ans = 0
    COMBinitialize(m)
    for i in range(K+1):
        ans += COMB(N-1+K-i, N-1) * pow(25, (K-i), MOD) * pow(26, i, MOD)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()
Problem p02642 (python)

Fixed submission:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    B = [True]*(10**6+1)

    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in set(A):
        if a not in bl and B[a]:
            ans += 1
        for i in range(1, 10**6):
            if 10**6 < a*i:
                break
            B[a*i] = False
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
from numba import njit, int32
import numpy as np


@njit(int32(int32[:], int32[:]))
def main(A, B):
    ans = 0

    for a in A:
        B[a] += 1

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            B[v] += 1
            v += a

    for a in A:
        if B[a] == 1:
            ans += 1

    return ans


if __name__ == '__main__':
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    ans = main(np.array(A), np.array(B))
    print(ans)

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    from math import gcd
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            L *= k
            bl.add(k)
    if c[1] == 1:
        return print(1)
    elif c[1] > 1:
        return print(0)
    A.sort()

    ans = 0
    L = 1
    for a in A:
        if a in bl:
            continue
        v = gcd(L, a)
        if v not in A:
            ans += 1
        L *= a
    print(ans)


if __name__ == '__main__':
    main()
Problem p02690 (python)

Fixed submission:
def main():
    X = int(input())
    for a in range(-200, 201):
        for b in range(-200, 201):
            if a**5 - b**5 == X:
                return print(a, b)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
from numba import njit


@njit
def main(X):
    for a in range(-2000, 2001):
        for b in range(-2000, 2001):
            if pow(a, 5) - pow(b, 5) == X:
                print(a, b)
                return


if __name__ == '__main__':
    X = int(input())
    main(X)
Problem p02786 (python)

Fixed submission:
def main():
    H = int(input())
    div = {2**i for i in range(40)}
    ans = 0
    from math import log2, ceil
    if not(H in div):
        for h in range(int(log2(H)) + 1):
            ans += 2**h
        print(ans)
    else:
        for h in range(int(log2(H)) + 1):
            ans += 2**h
        print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    H = int(input())
    div = {2**i for i in range(40)}
    ans = 0
    from math import log2, ceil
    if not(H in div):
        for h in range(int(log2(H)) + 1):
            ans += 2**h
        print(ans)
    else:
        for h in range(int(log2(H)) + 1):
            ans += 2**h
        print(ans)


if __name__ == '__main__':
    main()
Problem p02803 (python)

Fixed submission:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    st = [(h, w) for h in range(H) for w in range(W)]  # H*W個

    def bfs(sy, sx):
        que = deque()
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))

    ans = 0
    for s in st:
        dist = [[-1]*W for h in range(H)]
        if c[s[0]][s[1]] == "#":
            continue
        bfs(s[0], s[1])
        for t in st:
            if s == t or c[t[0]][t[1]] == "#":
                continue
            ans = max(ans, dist[t[0]][t[1]])
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    st = [(h, w) for h in range(H) for w in range(W)]

    def bfs(sy, sx, gy, gx):
        que = deque()
        dist = [[-1]*W for h in range(H)]
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))
        return dist[gy][gx]
    ans = 0
    for s in st:
        for t in st:
            if s == t or c[s[0]][s[1]] == "#" or c[t[0]][t[1]] == "#":
                continue
            ans = max(ans, bfs(*s, *t))
    print(ans)


if __name__ == '__main__':
    main()
Problem p02806 (python)

Fixed submission:
def main():
    N = int(input())
    A = [input().split() for i in range(N)]
    S = input()
    flag = False
    ans = 0
    for i, a in enumerate(A):
        if a[0] == S:
            flag = True
        elif flag:
            ans += int(a[1])
    print(ans)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    N = int(input())
    A = [input() for i in range(N)]
    S = input()
    print(sum(A[S.index():]))


if __name__ == '__main__':
    main()
Problem p02824 (python)

Fixed submission:
def main():
    N, M, V, P = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)

    def is_ok(mid):
        if mid <= P-1:
            return False  # 採用可能
        if A[mid] + M < A[P-1]:
            return True  # 採用不可能
        votable = M + (P-1) * M + (N - (mid + 1))*M
        for i in range(P-1, mid):
            votable += min(M, max(0, A[mid] + M - A[i]))
        if M*V <= votable:
            return False
        else:
            return True

    def binary_search_meguru():
        left = -1
        right = N
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right
    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    N, M, V, P = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)

    def is_ok1(mid, val):
        if val >= A[mid]:
            return True
        else:
            return False

    def is_ok2(mid, val):
        if val > A[mid]:
            return True
        else:
            return False

    def binary_search_meguru(val, is_ok):
        left = -1
        right = N
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid, val):
                right = mid
            else:
                left = mid
        return left

    not_ans = 0
    for i in range(N):
        top = A[i] + M
        upper = binary_search_meguru(top, is_ok1) + 1
        skip = 0
        if (-(V-1)) % N <= i+1:
            skip = 1
        if P <= upper:
            not_ans += 1
        elif A[-(V-1) + (P-1) - upper - skip] + M > top:
            top_less = P - 1
            top_less += max(0, N - binary_search_meguru(top, is_ok2) - 1)
            key = (V-1) - top_less
            mo = M % ((i-1)-(P-1))
            if i - mo <= key and top >= A[(P-1) + key] + M//((i-1)-(P-1) + 1) + 1:
                continue
            elif i - mo > key and top >= A[(P-1) + key] + M//((i-1)-(P-1) + 1):
                continue
            else:
                not_ans += 1

    print(N - not_ans)


if __name__ == '__main__':
    main()