Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)

def dfs(v,path):
  for u in g[v]:
    if check[u]==0:
      check[u]=1
      return dfs(u,path+[u])
  else:
    return path

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  u,v=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
check=[0]*(n+1)
check[1]=1
ans=dfs(1,[])[::-1]
ans+=[1]
ans+=dfs(1,[])
print(len(ans))
print(*ans)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

def dfs(v,path):
  for u in g[v]:
    if check[u]==0:
      check[u]=1
      path.append(u)
      return dfs(u,path)
  else:
    return path

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  u,v=map(int,input().split())
  g[u].append(v)
  g[v].append(u)
check=[0]*(n+1)
check[1]=1
ans=dfs(1,[])[::-1]
ans+=[1]
ans+=dfs(1,[])
print(len(ans))
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=int(input())
arr=[list(map(int,input().split())) for _ in range(q)]
color=[0]*(n+1)
for i in range(q):
  v,d,c=arr[i]
  tmp=0
  tq=collections.deque()
  tq.append((v,0,c))
  checked=[0]*(n+1)
  checked[v]=1
  color[v]=c
  while 1:
    if len(tq)==0:
      break
    tv,td,tc=tq.popleft()
    if td>=d:
      break
    for u in g[tv]:
      if checked[u]==0:
        checked[u]=1
        color[u]=tc
        tq.append((u,td+1,tc))
for i in range(1,n+1):
  print(color[i])

Fixed submission:
def dfs(i,v,d,c):
  if dp[v][d]==-1:
    dp[v][d]=i
    if d>0:
      dfs(i,v,d-1,c)
      for u in g[v]:
        dfs(i,u,d-1,c)
  
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
q=int(input())
arr=[]
for i in range(q):
  v,d,c=map(int,input().split())
  arr.append((i,v,d,c))
dp=[[-1]*11 for _ in range(n+1)]
for i,v,d,c in arr[::-1]:
  dfs(i,v,d,c)
ans=[]
for i in range(1,n+1):
  if dp[i][0]==-1:
    ans.append(0)
  else:
    ans.append(arr[dp[i][0]][3])
for i in range(n):
  print(ans[i])
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
pos1=[list(map(int,input().split())) for _ in range(n)]
pos2=[list(map(int,input().split())) for _ in range(m)]
ans=[0]*n
for i in range(n):
  lim=10**9
  for j in range(m):
    tmp=abs(pos1[i][0]-pos2[i][0])+abs(pos1[i][1]-pos2[i][1])
    if tmp<lim:
      tmp=lim
      ans[i]=j
for i in range(n):
  print(ans[i])

Fixed submission:
n,m=map(int,input().split())
pos1=[list(map(int,input().split())) for _ in range(n)]
pos2=[list(map(int,input().split())) for _ in range(m)]
ans=[0]*n
for i in range(n):
  lim=10**9
  for j in range(m):
    tmp=abs(pos1[i][0]-pos2[j][0])+abs(pos1[i][1]-pos2[j][1])
    if tmp<lim:
      lim=tmp
      ans[i]=j+1
for i in range(n):
  print(ans[i])
Buggy python submission (verdict: Runtime Error):
w,a,b=map(int,input().split())
if a<=b<=(a+w) or b<=(a+w)<=(b+w):
  print(0)
elif (a+w)<b:
  print(b-(a+w))
else:
  print(abs(a-(b+w))

Fixed submission:
w,a,b=map(int,input().split())
if a<=b<=(a+w) or b<=(a+w)<=(b+w):
  print(0)
elif (a+w)<b:
  print(b-(a+w))
else:
  print(abs(a-(b+w)))
Buggy python submission (verdict: Time Limit Exceeded):
n,ma,mb=map(int,input().split())
dp=[[0]*401 for _ in range(401)]
for _ in range(n):
  a,b,c=map(int,input().split())
  for i in range(400,-1,-1):
    for j in range(400,-1,-1):
      if i-a<0 or j-b<0:
        continue
      else:
        if dp[i-a][j-b]==0:
          continue
        else:
          if dp[i][j]==0:
            dp[i][j]=dp[i-a][j-b]+c
          else:
            dp[i][j]=min(dp[i][j],dp[i-a][j-b]+c)
  if dp[a][b]==0:
    dp[a][b]=c
  else:
    dp[a][b]=min(dp[a][b],c)
ans=10**10
for i in range(401):
  if i*ma>400 or i*mb>400:
    break
  if dp[i*ma][i*mb]==0:
    continue
  else:
    ans=min(ans,dp[i*ma][i*mb])
if ans==10**10:
  print(-1)
else:
  print(ans)

Fixed submission:
n,ma,mb=map(int,input().split())
dp=[[0]*401 for _ in range(401)]
for _ in range(n):
  a,b,c=map(int,input().split())
  for i in range(400,-1,-1):
    for j in range(400,-1,-1):
      if i-a<0 or j-b<0:
        continue
      else:
        if dp[i-a][j-b]==0:
          continue
        else:
          if dp[i][j]==0:
            dp[i][j]=dp[i-a][j-b]+c
          else:
            dp[i][j]=min(dp[i][j],dp[i-a][j-b]+c)
  if dp[a][b]==0:
    dp[a][b]=c
  else:
    dp[a][b]=min(dp[a][b],c)
ans=10**10
for i in range(401):
  if i*ma>400 or i*mb>400:
    break
  if dp[i*ma][i*mb]==0:
    continue
  else:
    ans=min(ans,dp[i*ma][i*mb])
if ans==10**10:
  print(-1)
else:
  print(ans)
Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
  if b==0:
    return a
  else:
    return(b,a%b)

n=int(input())
arr=list(map(int,input().split()))
sum1=sum(arr)
sum2=(n*(n+1))//2
cnt=sum1//sum2
if sum1%sum2!=0:
  print('NO')
else:
  s=set()
  l=n//(gcd(n,cnt))
  for val in arr:
    s.add(val%n)
  if len(s)==l:
    print('YES')
  else:
    print('NO')

Fixed submission:
n=int(input())
arr=list(map(int,input().split()))
if n==1:
  print('YES')
else:
  sum1=sum(arr)
  sum2=(n*(n+1))//2
  moves=sum1//sum2
  cnt=0
  if sum1%sum2!=0:
    print('NO')
  else:
    flag=True
    arr2=[]
    for i in range(n-1):
      tmp=arr[i]+moves
      if arr[i+1]==tmp:
        continue
      else:
        diff=tmp-arr[i+1]
        if diff%n!=0:
          flag=False
        else:
          arr2.append(n-i)
          cnt+=diff//n
          tmp=arr[i+1]-diff//n
          if tmp>n*(moves-diff//n):
            flag=False
    if flag==False:
      print('NO')
    else:
      if len(arr2)==moves:
        if arr[0]==sum(arr2):
          print('YES')
        else:
          print('NO')
      elif len(arr2)>moves:
        print('NO')
      else:
        if 1*(moves-len(arr2))<=arr[0]-sum(arr2)<=n*(moves-len(arr2)):
          print('YES')
        else:
          print('NO')
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecurtionlimit(10**9)

def dfs(v):
  if len(g[v])==0:
    return 0
  dic={}
  for u in g[v]:
    tmp=dfs(u)
    if tmp not in dic:
      dic[tmp]=1
    else:
      dic[tmp]+=1
  pos=max(dic.keys())
  return pos+dic[pos]

n=int(input())
g=[[] for _ in range(n+1)]
for i in range(n-1):
  v=int(input())
  g[v].append(i+2)
print(dfs(1))

Fixed submission:
import sys
sys.setrecursionlimit(10**9)

def dfs(v):
  if len(g[v])==0:
    return 0
  dic={}
  for u in g[v]:
    tmp=dfs(u)
    if tmp not in dic:
      dic[tmp]=1
    else:
      dic[tmp]+=1
  arr=[]
  for pos in dic.keys():
    arr+=[pos]*dic[pos]
  arr=sorted(arr,reverse=True)
  return max([(i+1)+arr[i] for i in range(len(arr))])

n=int(input())
g=[[] for _ in range(n+1)]
for i in range(n-1):
  v=int(input())
  g[v].append(i+2)
print(dfs(1))
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=input()
ans=0
for i in range(n):
  if s[i]='I':
    tmp=ans+1
  else:
    tmp=ans-1
  if tmp>ans:
    ans=tmp
print(ans)

Fixed submission:
n=int(input())
s=input()
res=0
ans=0
for i in range(n):
  if s[i]=='I':
    tmp=res+1
  else:
    tmp=res-1
  if tmp>ans:
    ans=tmp
  res=tmp
print(ans)
Buggy python submission (verdict: Runtime Error):
s=str(input())
s1=str[:5]
s2=str[6:13]
s3=str[14:]
print('{} {} {}'.format(s1,s2,s3))

Fixed submission:
s=str(input())
s1=s[:5]
s2=s[6:13]
s3=s[14:]
print('{} {} {}'.format(s1,s2,s3))

Buggy python submission (verdict: Runtime Error):
s=str(input())
s1=str[:5]
s2=str[6:12]
s3=str[14:]
print('{} {} {}'.format(s1,s2,s3))

Fixed submission:
s=str(input())
s1=s[:5]
s2=s[6:13]
s3=s[14:]
print('{} {} {}'.format(s1,s2,s3))
Buggy python submission (verdict: Runtime Error):
sx,sy,tx,ty=map(int,input().split())
w=tx-sx
h=ty-xy
ans=''
ans+='R'*w
ans+='U'*h
ans+='L'*w
ans+='D'*h
ans+='D'
ans+='R'*(h+1)
ans+='U'*(w+1)
ans+='L'
ans+='U'
ans+='L'*(h+1)
ans+='D'*(w+1)
ans+='R'
print(ans)

Fixed submission:
sx,sy,tx,ty=map(int,input().split())
w=tx-sx
h=ty-sy
ans=''
ans+='U'*h
ans+='R'*w
ans+='D'*h
ans+='L'*w
ans+='L'
ans+='U'*(h+1)
ans+='R'*(w+1)
ans+='D'
ans+='R'
ans+='D'*(h+1)
ans+='L'*(w+1)
ans+='U'
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a_i,a_o,a_t,a_j,a_l,a_s,a_z=map(int,input().split())
ans1=0
ans1+=a_o
ans2=0
for i in range(min(a_i,a_j,a_l)+1):
  tmp=3*i+2*((a_i-i)//2+(a_j-i)//2+(a_l-i)//2)
  ans2=max(ans2,tmp)
print(ans1+ans2)

Fixed submission:
a_i,a_o,a_t,a_j,a_l,a_s,a_z=map(int,input().split())
ans1=a_o
if min(a_i,a_j,a_l)==0:
  ans2=2*(a_i//2+a_j//2+a_l//2)
else:
  ans2=max(2*(a_i//2+a_j//2+a_l//2),3+2*((a_i-1)//2+(a_j-1)//2+(a_l-1)//2))
print(ans1+ans2)
Buggy python submission (verdict: Runtime Error):
a,b,c=map(str,input().split())
if b=='+':
  print(int(a)+int(b))
else:
  print(int(b)-int(b))

Fixed submission:
a,b,c=map(str,input().split())
if b=='+':
  print(int(a)+int(c))
else:
  print(int(a)-int(c))
Buggy python submission (verdict: Runtime Error):
n=int(input())
arr=list(map(int,input().split()))
if n%2==0:
  cnt=[0]*(n//2+1)
  for i in range(n):
    cnt[arr[i]//2]+=1
  if cnt[0]==1 and cnt.count(2)==n//2:
    print((2**(n//2))%(10**9+7))
  else:
    print(-1)
else:
  cnt=[0]*n//2
  for i in range(n):
    cnt[(arr[i]-1)//2]+=1
  if cnt.count(2)==n//2:
    print((2**(n//2))%(10**9+7))
  else:
    print(-1)

Fixed submission:
n=int(input())
arr=list(map(int,input().split()))
if n%2==1:
  cnt=[0]*(n//2+1)
  for i in range(n):
    cnt[arr[i]//2]+=1
  if cnt[0]==1 and cnt.count(2)==n//2:
    print((2**(n//2))%(10**9+7))
  else:
    print(0)
else:
  cnt=[0]*(n//2)
  for i in range(n):
    cnt[(arr[i]-1)//2]+=1
  if cnt.count(2)==n//2:
    print((2**(n//2))%(10**9+7))
  else:
    print(0)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input())
arr=list(map(int,input().split()))
ans=0
for i in range(1,n):
  if arr[i]+arr[i-1]<=k:
    continue
  elif arr[i-1]<=k<arr[i]+arr[i-1]:
    ans+=arr[i]+arr[i-1]-k
    arr[i]=k-arr[i-1]
  else:
    ans+=arr[i]
    arr[i]=0
    ans+=arr[i-1]-k
    arr[i-1]=k
print(ans)

Fixed submission:
n,k=map(int,input().split())
arr=list(map(int,input().split()))
ans=0
for i in range(1,n):
  if arr[i]+arr[i-1]<=k:
    continue
  elif arr[i-1]<=k<arr[i]+arr[i-1]:
    ans+=arr[i]+arr[i-1]-k
    arr[i]=k-arr[i-1]
  else:
    ans+=arr[i]
    arr[i]=0
    ans+=arr[i-1]-k
    arr[i-1]=k
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
arr=[(int(input()),i//n) for i in range(2*n)]
arr=sorted(arr,key=lambda x:x[0])
mod=10**9+7
ans=1
cnta=0
cntb=0
for pos,flag in arr:
  if flag==0:
    if cntb==0:
      cnta+=1
    else:
      cntb-=1
  else:
    if cnta>=1:
      ans*=cnt
      ans%=mod
      cnta-=1
    else:
      cntb+=1
print(ans)

Fixed submission:
n=int(input())
arr=[(int(input()),i//n) for i in range(2*n)]
arr=sorted(arr,key=lambda x:x[0])
mod=10**9+7
ans=1
cnta=0
cntb=0
for pos,flag in arr:
  if flag==0:
    if cntb==0:
      cnta+=1
    else:
      ans*=cntb
      ans%=mod
      cntb-=1
  else:
    if cnta==0:
      cntb+=1
    else:
      ans*=cnta
      ans%=mod
      cnta-=1
print(ans)

Buggy python submission (verdict: Runtime Error):
n=int(input())
arr=[(int(input()),i//n) for i in range(2*n)]
arr=sorted(arr,key=lambda x:x[0])
mod=10**9+7
ans=1
cnta=0
cntb=0
for pos,flag in arr:
  if flag==0:
    if cntb==0:
      cnta+=1
    else:
      cntb-=1
  else:
    if cnta>=1:
      ans*=cnt
      ans%=mod
      cnt-=1
    else:
      cntb+=1
print(ans)

Fixed submission:
n=int(input())
arr=[(int(input()),i//n) for i in range(2*n)]
arr=sorted(arr,key=lambda x:x[0])
mod=10**9+7
ans=1
cnta=0
cntb=0
for pos,flag in arr:
  if flag==0:
    if cntb==0:
      cnta+=1
    else:
      ans*=cntb
      ans%=mod
      cntb-=1
  else:
    if cnta==0:
      cntb+=1
    else:
      ans*=cnta
      ans%=mod
      cnta-=1
print(ans)

Buggy python submission (verdict: Runtime Error):
n=int(input())
arr=[(int(input())+i//n) for i in range(2*n)]
arr=sorted(arr,key=lambda x:x[0])
mod=10**9+7
ans=1
cnta=0
cntb=0
for pos,flag in arr:
  if flag==0:
    if cntb==0:
      cnta+=1
    else:
      cntb-=1
  else:
    if cnta>=1:
      ans*=cnt
      ans%=mod
      cnt-=1
    else:
      cntb+=1
print(ans)

Fixed submission:
n=int(input())
arr=[(int(input()),i//n) for i in range(2*n)]
arr=sorted(arr,key=lambda x:x[0])
mod=10**9+7
ans=1
cnta=0
cntb=0
for pos,flag in arr:
  if flag==0:
    if cntb==0:
      cnta+=1
    else:
      ans*=cntb
      ans%=mod
      cntb-=1
  else:
    if cnta==0:
      cntb+=1
    else:
      ans*=cnta
      ans%=mod
      cnta-=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
arr=[int(input()) for _ in range(n)]
ans=True
checked=[0]*n
num=0
for i in range(30,-1,-1):
  cnt=0
  pos=-1
  for j in range(n):
    if (arr[j])&(2**i)!=0:
      cnt+=1
      if arr[j]==2**i:
        pos=j
    arr[j]&=2**i-1
  if i!=0:
    if cnt%2==0:
      continue
    else:
      if pos==-1:
        ans=False
        break
      else:
        arr[pos]=2**i-1
        checked[pos]=1
        num+=1
        continue
  if i==0:
    if cnt%2==0:
      continue
    else:
      for j in range(n):
        if checked[j]==0:
          arr[j]-=1
          num+=1
          break
      else:
        ans=False
if ans==True:
  print(num)
else:
  print(-1)

Fixed submission:
n=int(input())
arr=[int(input()) for _ in range(n)]
ans=True
checked=[0]*n
num=0
for i in range(30,-1,-1):
  cnt=0
  pos=-1
  for j in range(n):
    if (arr[j])&(2**i)!=0:
      cnt+=1
      if arr[j]==2**i:
        pos=j
    arr[j]&=2**i-1
  if i!=0:
    if cnt%2==0:
      continue
    else:
      if pos==-1:
        ans=False
        break
      else:
        arr[pos]=2**i-1
        checked[pos]=1
        num+=1
        continue
  if i==0:
    if cnt%2==0:
      continue
    else:
      for j in range(n):
        if checked[j]==0:
          arr[j]-=1
          num+=1
          break
      else:
        ans=False
if ans==True:
  print(num)
else:
  print(-1)
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
disp=['A','B','C','D','E','F','G','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for i in range(h):
  arr=list(map(str,input.split()))
  for j in range(w):
    if arr[j]=='snuke':
      print(disp[j]+str(i))

Fixed submission:
h,w=map(int,input().split())
disp=['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
for i in range(h):
  arr=list(map(str,input().split()))
  for j in range(w):
    if arr[j]=='snuke':
      print(disp[j]+str(i+1))
Buggy python submission (verdict: Runtime Error):
h,w=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(h)]
pos="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for i in range(h):
  for j in range(w):
    if board[i][j]=="snuke":
      print(pos[j]+str(i+1))
      exit()

Fixed submission:
h,w=map(int,input().split())
board=[list(map(str,input().split())) for _ in range(h)]
pos="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for i in range(h):
  for j in range(w):
    if board[i][j]=="snuke":
      print(pos[j]+str(i+1))
      exit()
Buggy python submission (verdict: Runtime Error):
n,a=map(int,input().split())
costs=[10**18]*(n+1)
costs[1]=0
times=[0]*(n+1)
for i in range(1,n+1):
  times[i]=costs[i]+(n+i-1)//i
  for j in range(2,n//i+1):
    costs[i*j]=min(costs[i*j],costs[i]+j+a)
print(min(times[1:]))

Fixed submission:
n,a=map(int,input().split())
ans=10**18
for k in range(41):
  l=0
  r=n
  while r-l!=1:
    m=(r+l)//2
    if m**(k+1)>=n:
      r=m
    else:
      l=m
  for m in range(k+2):
    if (l**m)*(r**((k+1)-m))>=n:
      ans=min(ans,k*a+l*m+r*((k+1)-m))
print(ans)
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input())
dic={}
dic[a]=1
dic[b]=1
dic[c]=1
print(len(list(dic)))

Fixed submission:
a,b,c=map(int,input().split())
dic={}
dic[a]=1
dic[b]=1
dic[c]=1
print(len(list(dic)))
Buggy python submission (verdict: Runtime Error):
import collections

s=input()
n=len(s)
slen=collections.deque()
tlen=collections.deque()
cnt=0
ans=0
for i in range(n):
  if s[i]=='S':
    tpos=i
    break
else:
  tpos=n
for i in range(n-1,-1,-1):
  if s[i]=='T':
    spos=i
    break
else:
  spos=-1
s=s[tpos:spos+1]+'x'
for i in range(len(s)-1):
  cnt+=1
  if s[i]!=s[i+1]:
    if s[i]=='S':
      slen.append(cnt)
      cnt=0
    else:
      tlen.append(cnt)
      cnt=0
for i in range(len(slen)):
  stmp,ttmp=slen.popleft(),tlen.popleft()
  if stmp>ttmp:
    ans+=ttmp
    tmp=slen.popleft()+(stmp-ttmp)
    slen.appendleft(tmp)
  else:
    ans+=stmp
print(n-ans*2)

Fixed submission:
import collections

s=input()
n=len(s)
slen=collections.deque()
tlen=collections.deque()
cnt=0
ans=0
for i in range(n):
  if s[i]=='S':
    tpos=i
    break
else:
  tpos=n
for i in range(n-1,-1,-1):
  if s[i]=='T':
    spos=i
    break
else:
  spos=-1
s=s[tpos:spos+1]+'x'
for i in range(len(s)-1):
  cnt+=1
  if s[i]!=s[i+1]:
    if s[i]=='S':
      slen.append(cnt)
      cnt=0
    else:
      tlen.append(cnt)
      cnt=0
for i in range(len(slen)):
  stmp,ttmp=slen.popleft(),tlen.popleft()
  if stmp>ttmp:
    ans+=ttmp
    if len(slen)>0:
      tmp=slen.popleft()+(stmp-ttmp)
      slen.appendleft(tmp)
  else:
    ans+=stmp
print(n-ans*2)

Buggy python submission (verdict: Runtime Error):
import collections

s=input()
n=len(s)
slen=collections.deque()
tlen=collections.deque()
cnt=0
ans=0
for i in range(n):
  if s[i]=='S':
    tpos=i
    break
else:
  tpos=n
for i in range(n-1,-1,-1):
  if s[i]=='T':
    spos=i
    break
else:
  spos=-1
s=s[tpos:spos+1]+'x'
for i in range(len(s)-1):
  cnt+=1
  if s[i]!=s[i+1]:
    if s[i]=='S':
      slen.append(cnt)
      cnt=0
    else:
      tlen.append(cnt)
      cnt=0
for i in range(len(slen)):
  stmp,ttmp=slen.popleft(),tlen.popleft()
  if stmp>ttmp:
    ans+=ttmp
    tmp=stmp.popleft()+(stmp-ttmp)
    slen.appendleft(tmp)
  else:
    ans+=stmp
print(n-ans*2)

Fixed submission:
import collections

s=input()
n=len(s)
slen=collections.deque()
tlen=collections.deque()
cnt=0
ans=0
for i in range(n):
  if s[i]=='S':
    tpos=i
    break
else:
  tpos=n
for i in range(n-1,-1,-1):
  if s[i]=='T':
    spos=i
    break
else:
  spos=-1
s=s[tpos:spos+1]+'x'
for i in range(len(s)-1):
  cnt+=1
  if s[i]!=s[i+1]:
    if s[i]=='S':
      slen.append(cnt)
      cnt=0
    else:
      tlen.append(cnt)
      cnt=0
for i in range(len(slen)):
  stmp,ttmp=slen.popleft(),tlen.popleft()
  if stmp>ttmp:
    ans+=ttmp
    if len(slen)>0:
      tmp=slen.popleft()+(stmp-ttmp)
      slen.appendleft(tmp)
  else:
    ans+=stmp
print(n-ans*2)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
ans=0
arr=[0]
arr+=list(map(int,input().split()))
arr+=[0]
for i in range(1,n+1):
  tl=0
  tr=0
  for j in range(i-1,-1,-1):
    if arr[j]>arr[i]:
      tl+=1
    else:
      break
  for j in range(i+1,n+1):
    if arr[j]>arr[i]:
      tr+=1
    else:
      break
  ans+=arr[i]*(tl+1)*(tr+1)
print(ans)

Fixed submission:
n=int(input())
ans=0
arr=list(map(int,input().split()))
pos=[0]*(n+1)
for i in range(n):
  pos[arr[i]]=i
l=[i for i in range(n+1)]
r=[i for i in range(n+1)]
for i in range(n,0,-1):
  idx=pos[i]
  tl,tr=l[idx],r[idx]
  ans+=i*(idx-tl+1)*(tr-idx+1)
  l[tr+1]=tl
  r[tl-1]=tr
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
ans=0
arr=[0]
arr+=list(map(int,input().split()))
arr+=[0]
for i in range(1,n+1):
  tl=0
  tr=0
  for j in range(i-1,-1,-1):
    if arr[j]>arr[i]:
      tl+=1
    else:
      break
  for j in range(i+1,n+1):
    if arr[j]>arr[i]:
      tr+=1
    else:
      break
  ans+=arr[i]*(tl+1)*(tr+1)
print(ans)

Fixed submission:
n=int(input())
ans=0
arr=list(map(int,input().split()))
pos=[0]*(n+1)
for i in range(n):
  pos[arr[i]]=i
l=[i for i in range(n+1)]
r=[i for i in range(n+1)]
for i in range(n,0,-1):
  idx=pos[i]
  tl,tr=l[idx],r[idx]
  ans+=i*(idx-tl+1)*(tr-idx+1)
  l[tr+1]=tl
  r[tl-1]=tr
print(ans)
Buggy python submission (verdict: Runtime Error):
n,a=map(int,input().split())
arr=list(map(int,input().split()))
l=sum(arr)
dp=[[[0]*(l+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=arr[i-1]
  for j in range(0,i+1):
    for k in range(0,l+1):
      if k<xi:
        dp[i][j][k]=dp[i-1][j][k]
      elif j>=1:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-xi]
ans=0
for i in range(1,n+1):
  ans+=dp[n][i][i*a]
print(ans)

Fixed submission:
n,a=map(int,input().split())
arr=list(map(int,input().split()))
l=n*max(a,max(arr))
dp=[[[0]*(l+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=arr[i-1]
  for j in range(0,i+1):
    for k in range(0,l+1):
      if k<xi:
        dp[i][j][k]=dp[i-1][j][k]
      elif j>=1:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-xi]
ans=0
for i in range(1,n+1):
  ans+=dp[n][i][i*a]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,a=map(int,input().split())
arr=list(map(int,input().split()))
x=max(arr)
x=max(x,a)
dp=[[[0 for i in range(n*x+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=arr[i-1]
  for j in range(n+1):
    for k in range(n*x+1):
      if k<xi:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        if j>=1:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-xi]
ans=0
for i in range(1,n+1):
  ans+=dp[n][i][i*a]
print(ans)

Fixed submission:
n,a=map(int,input().split())
arr=list(map(int,input().split()))
l=n*max(a,max(arr))
dp=[[[0]*(l+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(1,n+1):
  xi=arr[i-1]
  for j in range(0,i+1):
    for k in range(0,l+1):
      if k<xi:
        dp[i][j][k]=dp[i-1][j][k]
      elif j>=1:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-xi]
ans=0
for i in range(1,n+1):
  ans+=dp[n][i][i*a]
print(ans)
Buggy python submission (verdict: Runtime Error):
def f(b,n):
  if b>n:
    return n
  else:
    return f(b,n//b)+n%b

n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  ans=0
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=0:
    print(ans)
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if f(tb,n)==s:
        ans=tb
        break
    if ans!=0:
      print(ans)
    else:
      print(-1)

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

def f(b,n):
  if b>n:
    return n
  else:
    return f(b,n//b)+n%b

n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  ans=10**18
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=10**18:
    print(ans)
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if tb==1:
        continue
      if f(tb,n)==s:
        ans=min(ans,tb)
    if ans!=10**18:
      print(ans)
    else:
      print(-1)

Buggy python submission (verdict: Runtime Error):
def f(b,n):
  if b>n:
    return n
  else:
    return f(b,n//b)+n%b

n=int(input())
s=int(input())
if s==n:
  print(n+1)
else:
  ans=0
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=0:
    print(ans)
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if f(tb,n)==s:
        ans=tb
        break
    if ans!=0:
      print(ans)
    else:
      print(-1)

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

def f(b,n):
  if b>n:
    return n
  else:
    return f(b,n//b)+n%b

n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  ans=10**18
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=10**18:
    print(ans)
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if tb==1:
        continue
      if f(tb,n)==s:
        ans=min(ans,tb)
    if ans!=10**18:
      print(ans)
    else:
      print(-1)