Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
black = [s=="#" for s in S]
ans = N - sum(black)
if sum(black)==0:
    ans = 0
for i in range(N):
    a = sum(black[:i])
    b = N-i-sum(black[i:])
    ans = min(ans,a+b)
print(ans)

Fixed submission:
from itertools import accumulate

N = int(input())
S = input()
black = [int(s=="#") for s in S]
white = [int(s==".") for s in S[::-1]]

a_black = [0]+list(accumulate(black))
a_white = list(accumulate(white))[::-1]+[0]

ans = 1000000
for b,w in zip(a_black,a_white):
    ans = min(ans, b+w)
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n = int(input())
cs = [int(input()) for _ in range(n)]

from collections import defaultdict
prev = -1
c_comp = []
# 連続する色はまとめて良い
for c in cs:
    if prev != c:
        c_comp.append(c)
    prev = c

d = defaultdict(list)
for i,c in enumerate(c_comp):
    d[c].append(i)


dp = [0] * 110000
mod = 10**9 + 7

# 何個目まで見たか
inds = defaultdict(int)
ans = 0
dp[0] = 1
for i,c in enumerate(c_comp):
    i_prev = d[c][inds[c]-1]
    if inds[c] >= 1:
        # かぶっていないそれ以前の場合の数を足す
        dp[i+1] += dp[i] + dp[i_prev+1]
    else:
        # 前の色が無い or 異なる場合はなにもしない
        dp[i+1] = dp[i]
    dp[i+1] %= mod
    inds[c] += 1
print(dp[len(c_comp)])

Fixed submission:
import sys
input = sys.stdin.readline
n = int(input())
cs = [int(input()) for _ in range(n)]

from collections import defaultdict
prev = -1
c_comp = []
# 連続する色はまとめて良い
for c in cs:
    if prev != c:
        c_comp.append(c)
    prev = c

d = defaultdict(list)
for i,c in enumerate(c_comp):
    d[c].append(i)


dp = [0] * 220000
mod = 10**9 + 7

# 何個目まで見たか
inds = defaultdict(int)
ans = 0
dp[0] = 1
for i,c in enumerate(c_comp):
    i_prev = d[c][inds[c]-1]
    if inds[c] >= 1:
        # かぶっていないそれ以前の場合の数を足す
        dp[i+1] += dp[i] + dp[i_prev+1]
    else:
        # 前の色が無い or 異なる場合はなにもしない
        dp[i+1] = dp[i]
    dp[i+1] %= mod
    inds[c] += 1
print(dp[len(c_comp)])
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
print(int(bin(N^M),2)

Fixed submission:
N,M = map(int,input().split())
def xor_sum(N):
    N+=1
    value = 0
    value += (N//2)%2 # 2^0の位
    for i in range(1,40):
        # print(N%(2**(i+1))-2**i)
        cnt = max(0,N%(2**(i+1))-2**i) #mod2^(i+1)のcnt
        value += (cnt%2) * 2**i
    return value

# print(xor_sum(3))
print(xor_sum(M)^xor_sum(N-1))
Buggy python submission (verdict: Runtime Error):
A,B,K = map(int,input().split())
cnt = 1
l = []
for i in range(2,max(A+1,B+1)):
    if A%i == 0 and B%i == 0:
        l.append(i)
if K == 1:
    ans = 1
else:
    ans = l[-K]
print(ans)

Fixed submission:
A,B,K = map(int,input().split())
cnt = 0
l = []
for i in range(max(A+1,B+1),0,-1):
    if A%i == 0 and B%i == 0:
        cnt +=1
        if cnt == K:
            ans = i
            break
print(ans)
Buggy python submission (verdict: Runtime Error):

"""
dp[i] : 足場iに到達するにあたって、たどり着く最小回数
"""
INF = 10**10
dp = [INF]*11000
N = int(input())
hs  = list(map(int, input().split())) + [INF,INF]
dp[0] = 0
for i in range(N):
    dp[i+1] = min(dp[i+1], dp[i]+abs(hs[i+1]-hs[i]))
    dp[i+2] = min(dp[i+2], dp[i]+abs(hs[i+2]-hs[i]))
print(dp[N-1])

      

Fixed submission:
import numpy as np
N = int(input())
hs = [int(i) for i in input().split()]
dp = np.zeros(N)
for i,h in enumerate(hs):
    if i == 0:        
        # 0は初期化されている
        dp[i] = 0
        continue
    elif i == 1:
        # 1は1通りしか無い
        dp[i] = dp[i-1] + abs(hs[i-1]-h)
    else:
        # 1個前か2個前で、コストが最小になるやつ
        dp[i] = min(dp[i-1]+abs(hs[i-1]-h),dp[i-2]+abs(hs[i-2]-h))
# print(dp)
print(int(dp[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i] : 足場i番目におけるコストの最小値
"""

N,K = map(int, input().split())
hs = list(map(int, input().split()))
INF = 10**10
dp = [INF]*110000
dp[0] = 0
for i in range(N):
    for j in range(K+1):
        #もらうDP
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i-j]+abs(hs[i-j]-hs[i]))
print(dp[N-1])

Fixed submission:
N, K = map(int,input().split())
hs = [int(i) for i in input().split()]

dp = [1000000]*N
dp[0] = 0
for i in range(1,N):
    # for k in range(K+1):
    x = max(0, i-K)
    # dp[i] = min(dp[i], dp[min_ind]+abs(hs[min_ind]-hs[i]))
    dp[i] = min([dpj + abs(hs[i] - hj) for hj, dpj in zip(hs[x:i], dp[x:i])])
# print(dp)
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):

"""
dp[i] i番目に到達するときの最小値
遷移
送るDP
i-1段目まで下記を実施
dp[i+1] = min(dp[i+1], dp[i]+コスト)
if (一段飛ばしできる余地があれば): 
    dp[i+2] = min(dp[i+2],dp[i]+コスト)

"""
N, K = map(int, input().split())
hs = list(map(int, input().split()))

INF = 10**12
dp = [INF]*101000
dp[0] = 0

for i in range(1,N):
    for j in range(1,K+1):
        if i-j >= 0:
            cost = abs(hs[i]-hs[i-j])
            dp[i] = min(dp[i],dp[i-j]+cost)

print(dp[N-1])

Fixed submission:
N, K = map(int,input().split())
hs = [int(i) for i in input().split()]

dp = [1000000]*N
dp[0] = 0
for i in range(1,N):
    # for k in range(K+1):
    x = max(0, i-K)
    # dp[i] = min(dp[i], dp[min_ind]+abs(hs[min_ind]-hs[i]))
    dp[i] = min([dpj + abs(hs[i] - hj) for hj, dpj in zip(hs[x:i], dp[x:i])])
# print(dp)
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
N, K = map(int,input().split())
hs = [int(i) for i in input().split()]

dp = [1000000]*N
dp[0] = 0
for i in range(1,N):
    min_ind = max(0, i-K)
    dp[i] = min(dp[i], dp[min_ind]+abs(hs[min_ind]-hs[i]))
    for k in range(1,K+1):
        dp[i] = min(dp[i], dp[i-k]+abs(hs[i-k]-hs[i]))

print(dp[-1])

Fixed submission:
N, K = map(int,input().split())
hs = [int(i) for i in input().split()]

dp = [1000000]*N
dp[0] = 0
for i in range(1,N):
    # for k in range(K+1):
    x = max(0, i-K)
    # dp[i] = min(dp[i], dp[min_ind]+abs(hs[min_ind]-hs[i]))
    dp[i] = min([dpj + abs(hs[i] - hj) for hj, dpj in zip(hs[x:i], dp[x:i])])
# print(dp)
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int, input().split())

INF = 10**10
vsum = 1000*N
dp = [INF for i in range(vsum+1)]
dp[0] = 0


for _ in range(N):
    w,v = map(int,input().split())
    dp1 = [d for d in dp]
    for i,d in enumerate(dp):
        if d == INF:
            continue
        else:
            if i + v <= vsum:
                dp[i+v] = min(dp1[i+v], dp1[i]+w)
    
ans = 0
for i,d in enumerate(dp):
    if d <= W:
        ans = i

print(ans)

Fixed submission:
import numpy as np
N,W = map(int, input().split())
INF =  10**10
V_max = 100001
N_max = 101
# dp = np.ones((N_max,V_max), dtype=np.int64)*INF
dp = np.ones(V_max,dtype=np.int64)*INF
dp[0] = 0
for i in range(N):
    a = np.ones(V_max)*INF
    w,v = map(int,input().split())
    # np.minimum(dp[i][:-v]+w,dp[i][v:],out=dp[i+1][v:])
    np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])
ans = 0
for i,d in enumerate(dp):
    if d<=W:
        ans = i
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,W = map(int, input().split())

INF = 10**10
vsum = 10**5
dp = [INF for i in range(vsum+1)]
dp[0] = 0

for _ in range(N):
    w,v = map(int,input().split())
    dp1 = [d for d in dp]
    for i,d in enumerate(dp):
        if d == INF:
            continue
        else:
            if i + v <= vsum:
                dp1[i+v] = min(dp[i+v], dp[i]+w)
    dp = [d1 for d1 in dp1]

ans = 0
for i,d in enumerate(dp):
    if d <= W:
        ans = i

print(ans)


Fixed submission:
import numpy as np
N,W = map(int, input().split())
INF =  10**10
V_max = 100001
N_max = 101
# dp = np.ones((N_max,V_max), dtype=np.int64)*INF
dp = np.ones(V_max,dtype=np.int64)*INF
dp[0] = 0
for i in range(N):
    a = np.ones(V_max)*INF
    w,v = map(int,input().split())
    # np.minimum(dp[i][:-v]+w,dp[i][v:],out=dp[i+1][v:])
    np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])
ans = 0
for i,d in enumerate(dp):
    if d<=W:
        ans = i
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
"""
dp[i][j] : i番目において、(表-裏)+N=j
dp[i+1][j+1] : dp[i][j] * (表)
dp[i+1][j-1] : dp[i][j] * (裏)
"""
N = int(input())
ps = list(map(float, input().split()))

dp = [[0]*(2*N+1) for i in range(N+1)]
dp[0][N] = 1
for i,p in enumerate(ps):
    for j in range(2*N):
        dp[i+1][j-1] += dp[i][j] * (1-p)
        dp[i+1][j+1] += dp[i][j] * p
    # print(dp[i+1])
print(sum(dp[N][N:]))

Fixed submission:
"""
dp[i][j] : i番目において、(表-裏)+N=j
dp[i+1][j+1] : dp[i][j] * (表)
dp[i+1][j-1] : dp[i][j] * (裏)
"""
N = int(input())
ps = list(map(float, input().split()))

dp = [[0]*(2*N+1) for i in range(N+1)]
dp[0][N] = 1
for i,p in enumerate(ps):
    for j in range(2*N):
        dp[i+1][j-1] += dp[i][j] * (1-p)
        dp[i+1][j+1] += dp[i][j] * p
    # print(dp[i+1])
print(sum(dp[N][N:]))
Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
data = np.zeros((N,3))
for i in range(N):
    data[i] = np.array(input().split())

for n in range(10201):
    C_x = n // 101
    C_y = n % 101
    correctflg = True
    unsetflg = True
    for i,(x,y,h) in enumerate(data):
        if unsetflg:
            if h >= 1:
                H = abs(x-C_x)+abs(y-C_y)+h
                unsetflg = False
        else:
            if h >= 1 and H != abs(x-C_x)+abs(y-C_y)+h:
                correctflg = False
                break 
    if correctflg:
        print(C_x,C_y,int(H))
        break
    
            
            


Fixed submission:
N = int(input())
if N == 1:
    print("Hello World")
else:
    A = int(input())
    B = int(input())
    print(A+B)
Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
data = np.zeros((N,3))
for i in range(N):
    data[i] = np.array(input().split())

# data = np.array([[2,3,5],[2,1,5],[1,2,0],[3,2,5]])

for n in range(10201):
    C_x = n // 101
    C_y = n % 101
    flg = True
    unsetflg = True
    for i,(x,y,h) in enumerate(data):
        if unsetflg and h>=1:
            H = abs(x-C_x)+abs(y-C_y)+h
            unsetflg = False
        else
            if h>=1 and H != abs(x-C_x)+abs(y-C_y)+h:
                flg = False
                break 
    if flg:
        print(C_x,C_y,int(H))
        break
    
            
            


Fixed submission:
import numpy as np
N = int(input())
data = np.zeros((N,3))
for i in range(N):
    data[i] = np.array(input().split())

# data = np.array([[2,3,0],[2,1,0],[1,2,0],[3,2,5]])

if len(np.where(data[:,2]!=0)[0]) == 1:
    C_x, C_y, H = map(int,data[np.where(data[:,2]!=0)[0][0]])
    print(C_x, C_y, H)
else:
    for n in range(10201):
        C_x = n // 101
        C_y = n % 101
        correctflg = True
        unsetflg = True
        for x,y,h in data:
            if unsetflg:
                if h >= 1:
                    H = abs(x-C_x)+abs(y-C_y)+h
                    unsetflg = False
            else:
                if h >= 1 and H != abs(x-C_x)+abs(y-C_y)+h:
                    correctflg = False
                    break 
        if correctflg:
            print(C_x,C_y,int(H))
            break

Buggy python submission (verdict: Runtime Error):
import numpy as np
# N = int(input())
# data = np.zeros((N,3))
# for i in range(N):
#     data[i] = np.array(input().split())

data = np.array([[2,3,5],[2,1,5],[1,2,5],[3,2,5]])

for n in range(10201):
    C_x = n // 101
    C_y = n % 101
    flg = True
    unsetflg = True
    for i,(x,y,h) in enumerate(data):
        if unsetflg
        	if h>0:
            	H = abs(x-C_x)+abs(y-C_y)+h
            	unsetflg = False
        elif h>0:
            if H != abs(x-C_x)+abs(y-C_y)+h:
                flg = False
                break 
    if flg:
        print(C_x,C_y,int(H))
        break
          

Fixed submission:
import numpy as np
N = int(input())
data = np.zeros((N,3))
for i in range(N):
    data[i] = np.array(input().split())

# data = np.array([[2,3,0],[2,1,0],[1,2,0],[3,2,5]])

if len(np.where(data[:,2]!=0)[0]) == 1:
    C_x, C_y, H = map(int,data[np.where(data[:,2]!=0)[0][0]])
    print(C_x, C_y, H)
else:
    for n in range(10201):
        C_x = n // 101
        C_y = n % 101
        correctflg = True
        unsetflg = True
        for x,y,h in data:
            if unsetflg:
                if h >= 1:
                    H = abs(x-C_x)+abs(y-C_y)+h
                    unsetflg = False
            else:
                if h >= 1 and H != abs(x-C_x)+abs(y-C_y)+h:
                    correctflg = False
                    break 
        if correctflg:
            print(C_x,C_y,int(H))
            break
Buggy python submission (verdict: Runtime Error):
# 最大公約数なきがするけど。
def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

N, X = map(int,input().split())
xs = [int(i) for i in input().split()]
xs.append(X)
xs = sorted(xs)
diffs = [xs[i]-xs[i-1] for i in range(1,len(xs))] #差を取る
gcd_min = gcd(diffs[0],diffs[1])
for i in range(2,len(diffs)):
    gcd_min = gcd(gcd_min, diffs[i])

print(gcd_min)

Fixed submission:
# 最大公約数なきがするけど。
def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

N, X = map(int,input().split())
xs = [int(i) for i in input().split()]

xs.append(X)
xs = sorted(xs)
if len(xs) == 2:
    print(abs(xs[0]-xs[1]))
else:
    diffs = [xs[i]-xs[i-1] for i in range(1,len(xs))] #差を取る
    gcd_min = gcd(diffs[0],diffs[1])
    for i in range(2,len(diffs)):
        gcd_min = gcd(gcd_min, diffs[i])

    print(gcd_min)
Buggy python submission (verdict: Runtime Error):
"""
07:26:30
奇数が2つで2つの偶数になる
片方どちらかが1の場合は、奇数が2つで1つの偶数になる
0でswapは分断される
H,W<=500なので全探索？O(HW)くらいか
端っこから決めていく
"""

H, W  = map(int, input().split())
right = []
ans = []
for i in range(H):
    As = list(map(int, input().split()))
    for j in range(W-1):
        if As[j]%2 == 1:
            ans.append([i+1,j+1,i+1,j+1+1])
            As[j] -= 1
            As[j+1] += 1
    right.append(As[j+1])
for i in range(H-1):
    if right[i]%2 == 1:
        ans.append([i+1,j+1,i+1+1,j+1])
        right[i] -= 1
        right[i+1] += 1
print(len(ans))
for a in ans:
    print(*a)



Fixed submission:
### 予め一筆書きルートを作る
H, W = map(int,input().split())
As = []
for i in range(H):
    As.append(list(map(int,input().split())))
routes = []
for i in range(H):
    for j in range(W):
        if i%2 == 0:
            routes.append((i+1,j+1))
        else:
            routes.append((i+1,W-j))
n = len(routes)
mvs = []
cnt = 0
for i in range(n-1):
    hi,wi = routes[i]
    hi2,wi2 = routes[i+1]
    if As[hi-1][wi-1] % 2 == 1:
        As[hi2-1][wi2-1] += 1
        mvs.append([hi,wi,hi2,wi2])
        cnt += 1

print(cnt)
for h1,w1,h2,w2 in mvs:
    print(h1,w1,h2,w2)

Buggy python submission (verdict: Runtime Error):

H, W  = map(int, input().split())
right = []
ans = []
for i in range(H):
    As = list(map(int, input().split()))
    for j in range(W-1):
        if As[j]%2 == 1:
            ans.append([i+1,j+1,i+1,j+1+1])
            As[j] -= 1
            As[j+1] += 1
    right.append(As[j])

for i in range(H-1):
    if right[i]%2 == 1:
        ans.append([i+1,j+1,i+1+1,j+1])
print(len(ans))
for a in ans:
    print(*a)


Fixed submission:
### 予め一筆書きルートを作る
H, W = map(int,input().split())
As = []
for i in range(H):
    As.append(list(map(int,input().split())))
routes = []
for i in range(H):
    for j in range(W):
        if i%2 == 0:
            routes.append((i+1,j+1))
        else:
            routes.append((i+1,W-j))
n = len(routes)
mvs = []
cnt = 0
for i in range(n-1):
    hi,wi = routes[i]
    hi2,wi2 = routes[i+1]
    if As[hi-1][wi-1] % 2 == 1:
        As[hi2-1][wi2-1] += 1
        mvs.append([hi,wi,hi2,wi2])
        cnt += 1

print(cnt)
for h1,w1,h2,w2 in mvs:
    print(h1,w1,h2,w2)
Buggy python submission (verdict: Time Limit Exceeded):
"""
累積和っぽい

始点と終点の"2"つを指定しなければいけない
⇨二次元累積和ってやつ。

参考
https://qiita.com/drken/items/56a6b68edef8fc605821
"""

import numpy as np
N,M,Q = map(int,input().split())
A = np.zeros((N+1,N+1))
Acum = np.zeros((N+1,N+1))

for _ in range(M):
    L,R = map(int,input().split())
    A[L-1][R-1] += 1

#2次元累積和
for i in range(N):
    for j in range(N):
        Acum[i+1][j+1] = Acum[i][j+1] + Acum[i+1][j] - Acum[i][j] + A[i][j]

# print(Acum)
for _ in range(Q):
    p,q= map(int,input().split())
    A = Acum[q,q]-Acum[p-1,q]-Acum[q,p-1]+Acum[p-1,p-1]
    print(int(A))

Fixed submission:
N,M,Q = map(int,input().split())
A = [[0 for i in range(N+1)] for j in range(N+1)]
Acum = [[0 for i in range(N+1)] for j in range(N+1)]

for _ in range(M):
    L,R = map(int,input().split())
    A[L-1][R-1] += 1

#2次元累積和
for i in range(N):
    for j in range(N):
        Acum[i+1][j+1] = Acum[i][j+1] + Acum[i+1][j] - Acum[i][j] + A[i][j]

# print(Acum)
for _ in range(Q):
    p,q= map(int,input().split())
    A = Acum[q][q]-Acum[p-1][q]-Acum[q][p-1]+Acum[p-1][p-1]
    print(A)
Buggy python submission (verdict: Runtime Error):
from operator import itemgetter
bridges = []
for i in range(M):
    bridges.append(list(map(int, input().split())))
bridges.sort(key=itemgetter(1))
b_right = 0
cnt = 0
for a,b in bridges:
    if a > b_right:
        b_right = b - 1
        cnt += 1
print(cnt) 


Fixed submission:
"""
- N個の島とN-1個の橋
- i番目の橋は島iと島i+1を接続する
- ai番目とbi番目の島の間での諍いを止めたい
    - aiとbi番目の島を隔離する
- こんな要望がM個

始点と終点が必要そうだから、2次元に値を保存してみる⇨遅い。ダメ
"""
import heapq
N,M = map(int, input().split())

# たくさん値を持っておく必要はない
# 左端を固定しながら、右端の一番近いところを算出していく
# 一番近いところを切れれば、それより遠いところも自ずと切れる
dic = {}
for i in range(M):
    a, b = map(int, input().split())
    if a not in dic or dic[a] > b:
        dic[a] = b

# 条件が厳しい右から考えていくパターン
# a,bで考えて,まだ着られていない(最後に切られたposより右にある)なら、aで切る(最も左端)
# 切った左端よりも左側にあるならもう一回切る必要がある。そうじゃないなら切る必要なし
cnt = 0
pos = 1000000000000
for j in sorted(dic.keys(),reverse=True): # 降順に並べる(右側から)
    if dic[j] <= pos:
        cnt += 1
        pos = j
print(cnt)
Buggy python submission (verdict: Runtime Error):
def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

n = input()
print(2*n/gcd(2,n))

Fixed submission:
def gcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return a

n = int(input())
print(2*n//gcd(2,n))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int, input().split()))
res = 0
for l in range(N):
    val = As[l]
    cnt = 1
    r = l+1
    while (r < N and val^As[r] == val+As[r]):
        # print(l,r,val)
        val += As[r]
        cnt += 1
        r += 1
    res += cnt
    # print(l,cnt)
print(res)



Fixed submission:
"""
多分またバグらせる
"""
# 尺取

N = int(input())
As = list(map(int, input().split()))
res = 0
l,r = 0, 0
val = As[l]
for l in range(N):
    cnt = 0
    # 区間が1のときは確定でOKなので+1する
    if l == r:
        r += 1
        val = As[l]
    # 差分が1以上(実質、区間が2つ以上存在するとき)
    elif r-(l-1) > 1:
        val -= As[l-1]
    # 条件を満たすうちは尺を伸ばす
    # print("be","l",l,"r",r,"val",val)
    while (r < N and val^As[r] == val+As[r]):
        val += As[r]
        r += 1
    # print("af","l",l,"r",r,"val",val)
    # 条件が終了したら差分を加える
    res += (r-l)
print(res)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int, input().split()))
res = 0
for l in range(N):
    val = As[l]
    cnt = 1
    r = l+1
    while (r < N and val^As[r] == val+As[r]):
        # print(l,r,val)
        val += As[r]
        cnt += 1
        r += 1
    res += cnt
    # print(l,cnt)
print(res)



Fixed submission:
"""
多分またバグらせる
"""
# 尺取

N = int(input())
As = list(map(int, input().split()))
res = 0
l,r = 0, 0
val = As[l]
for l in range(N):
    cnt = 0
    # 区間が1のときは確定でOKなので+1する
    if l == r:
        r += 1
        val = As[l]
    # 差分が1以上(実質、区間が2つ以上存在するとき)
    elif r-(l-1) > 1:
        val -= As[l-1]
    # 条件を満たすうちは尺を伸ばす
    # print("be","l",l,"r",r,"val",val)
    while (r < N and val^As[r] == val+As[r]):
        val += As[r]
        r += 1
    # print("af","l",l,"r",r,"val",val)
    # 条件が終了したら差分を加える
    res += (r-l)
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
A, B, K = map(int, input().split())

a = [i for i in range(A,B+1)]
if B-A+1 <= 2*K:
    for ans in a:
        print(ans)
else:
    for ans in a[:K]:
        print(ans)
    for ans in a[-K:]:
        print(ans)


Fixed submission:
A, B, K = map(int, input().split())

if B-A+1 <= 2*K:
    for ans in range(A,B+1):
        print(ans)
else:
    for ans in range(A, A+K):
        print(ans)
    for ans in range(B-K+1, B+1):
        print(ans)

Buggy python submission (verdict: Runtime Error):
A, B, K = map(int, input().split())

a = list(range(A,B+1))
if B-A+1 <= 2*K:
    for ans in a:
        print(ans)
else:
    for ans in a[:K]:
        print(ans)
    for ans in a[-K:]:
        print(ans)


Fixed submission:
A, B, K = map(int, input().split())

if B-A+1 <= 2*K:
    for ans in range(A,B+1):
        print(ans)
else:
    for ans in range(A, A+K):
        print(ans)
    for ans in range(B-K+1, B+1):
        print(ans)
Buggy python submission (verdict: Runtime Error):
"""
N/x-1 - N/x >= 1のところを狙っていく
解aだとして、aまではAを+1ずつインクリメントでOK
a以降はN/aからbをデクリメント
"""
N = int(input())

def calc(a,b):
    N = a * b
    n = int((N-1)**0.5)
    cnta = n
    cntb = n
    if a <= n:
        cnta -= 1
    if b <= n:
        cntb -= 1
    ans = cnta + cntb
    if (N-1)//n == n:
        ans -= 1
    # print("cnt",cnta,cntb)
    print(ans)        

for i in range(N):
    a,b = map(int, input().split())
    ans = calc(a,b)


Fixed submission:
"""
N/x-1 - N/x >= 1のところを狙っていく
解aだとして、aまではAを+1ずつインクリメントでOK
a以降はN/aからbをデクリメント
"""
N = int(input())

def calc(a,b):
    N = a * b 
    n = int(N**0.5)-2
    while (n+1)**2 < N:
        n += 1
    if a == b == 1:
        return 0
    cnta = n
    cntb = n
    if a <= n:
        cnta -= 1
    if b <= n:
        cntb -= 1
    ans = cnta + cntb
    # A : 1,2,3,..,n,n+1, 大きい数
    # B : 大きい数,n+1,n,...,3,2,1
    # それぞれペアを見つけながら進んでいけばいいので基本 2*n
    # 1. Aの1~nまでにaが入っていると-1
    # 2. Bの1~nまでにbが入っていると-1
    # 3. n*n+1がabより大きいと成り立たないので-1
    if n*(n+1) >= N:
        ans -= 1
    return ans        

for i in range(N):
    a,b = map(int, input().split())
    ans = calc(a,b)
    print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
if N > M:
    tmp = N
    N = M
    M = tmp
fields = [[0] * (M+2) for i in range(N+2)]

# for i in range(1,N+1):
#     for j in range(1,M+1):
#         for k in range(-1,2):
#             for l in range(-1,2):
#                 fields[i+k][j+l] += 1

# for f in fields:
#     print(*f)

n9 = max(0,N-2)*max(0,M-2)
n1 = 4
n2 = 8
n3 = max(0,N-2)*2 + max(0,M-2)*2
n6 = max(0,N-2)*2 + max(0,M-2)*2
n4 = 4

# N <= M としても一般性を失わない
if N == 1:
    if M == 1:
        print(1)
    elif M == 2:
        print(0)
    else:
        print(M-2)
elif N == 2:
    print(0)
else:
    print(n9)


Fixed submission:
N, M = map(int, input().split())
if N > M:
    tmp = N
    N = M
    M = tmp

# N <= M としても一般性を失わない
if N == 1:
    if M == 1:
        print(1)
    elif M == 2:
        print(0)
    else:
        print(M-2)
elif N == 2:
    print(0)
else:
    print((N-2)*(M-2))
Buggy python submission (verdict: Runtime Error):
n = int(input())
As = list(map(int, input().split()))
    
def f(m):
    debug = m
    for a in As:
        i = m // a
        m = i * a
    return m

# 二部探索?
l = 1
r = 10**5+1
while r-l > 1:
    m = (r+l)//2
    if f(m) <= 1: l = m
    else: r = m
ans1 = r
l = 1
r = 10**5 + 1
while r-l > 1:
    m = (r+l)//2
    if f(m) <= 2: l= m
    else: r = m
ans2 = l

if ans1 >= ans2:
    print(-1)
else:
    print(ans1[1],ans2[0])

Fixed submission:
K = int(input())
As = list(map(int, input().split()))

def f(n):
    for a in As:
        n = a * (n//a)
    return n

ng,ok = 1, 10**20
while ok-ng > 1:
    m = (ok+ng)//2
    if f(m) >= 2: #2以上ならTrue
        ok = m
    else:
        ng = m
mn = ok
# print(ng,ok)

ok,ng = 1, 10**20
while ng-ok > 1:
    m = (ok+ng)//2
    if f(m) <= 2: #2以下の範囲
        ok = m
    else:
        ng = m
mx = ok

# print(ok,ng)
if mn > mx:
    print(-1)
else:
    print(mn,mx)