Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
import bisect
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            y=bisect.bisect_right(l,b-a)
            for k in range(y,x):
                c=l[k]
                if a<b and b<c:
                    ans+=1
print(ans)


Fixed submission:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
import bisect
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            y=bisect.bisect_right(l,b-a)
            if b-a>=a:
                ans+=max(0,x-y-1)
            else:
                ans+=max(0,x-y-2)
print(ans//3)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=list(map(int,input().split()))
l.sort()
from collections import Counter
cou=Counter(l)
ll=[]
for i in range(n):
    if not l[i] in ll:
        ll.append(l[i])

ans=0
for i in range(len(cou)):
    x=cou[i]
    if x>=3:
        ans+=(x*(x-1)*(x-2)//6)

import bisect

ans2=0
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            for k in range(x):
                if k==i or k==j:
                    continue
                else:
                    c=l[k]
                    if a<(b+c) and b<(a+c) and c<(a+b):
                        ans2+=(cou[a]*cou[b]*cou[c])

print(ans+(ans2//3))


Fixed submission:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
import bisect
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            y=bisect.bisect_right(l,b-a)
            if b-a>=a:
                ans+=max(0,x-y-1)
            else:
                ans+=max(0,x-y-2)
print(ans//3)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
import bisect
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            for k in range(x):
                if k==i or k==j:
                    continue
                else:
                    c=l[k]
                    if a<(b+c) and b<(a+c) and c<(a+b):
                        ans+=1
print(ans//3)


Fixed submission:
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
import bisect
for i in range(n):
    for j in range(n):
        if i<j:
            a=l[i]
            b=l[j]
            x=bisect.bisect_left(l,a+b)
            y=bisect.bisect_right(l,b-a)
            if b-a>=a:
                ans+=max(0,x-y-1)
            else:
                ans+=max(0,x-y-2)
print(ans//3)
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

def sosu(n):
    pn=[2]
    for i in range(3,n+1):
        chk=True
        for j in pn:
            if i%j==0:
                chk=False
        if chk:
            pn.append(i)
    return pn


a,b=map(int,input().split())
x=gcd(a,b)
l=sosu(x)
ans=1
for m in l:
    if x%m==0:
        ans+=1
print(ans)


Fixed submission:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

a,b=map(int,input().split())
x=gcd(a,b)
l=factorization(x)
ans=1
ans+=len(l)
if x==1:
    print(1)
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000)
n,q=map(int,input().split())
g=[[i] for i in range(n+1)]

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

c=[0]*(n+1)
def dfs(p,x):
    for i in g[p]:
        if r[i]:
            r[i]=0
            c[i]+=x
            dfs(i,x)

for _ in range(q):
    r=[1]*(n+1)
    p,x=map(int,input().split())
    dfs(p,x)


print(*c[1:])


Fixed submission:
a=int(input())
s=input()
if a>=3200:
    print(s)
else:
    print("red")
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000)
n,q=map(int,input().split())
g=[[i] for i in range(n+1)]

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

c=[0]*(n+1)
def dfs(p,x):
    for i in g[p]:
        if r[i]:
            r[i]=0
            c[i]+=x
            dfs(i,x)

for _ in range(q):
    r=[1]*(n+1)
    p,x=map(int,input().split())
    dfs(p,x)


print(*c[1:])


Fixed submission:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)

n,q=map(int,input().split())
g=[[] for _ in range(n+1)]

for _ in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
c=[0]*(n+1)
que=[1]
done=[0]*(n+1)
done[1]=1
for _ in range(q):
    p,x=map(int,input().split())
    c[p]+=x
while que:
    d=que.pop()
    for node in g[d]:
        if not done[node]:
            c[node]+=c[d]
            que.append(node)
            done[node]+=1
print(*c[1:])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000)
n,q=map(int,input().split())
g=[[i] for i in range(n+1)]

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

c=[0]*(n+1)
def dfs(p,x):
    for i in g[p]:
        if r[i]:
            r[i]=0
            c[i]+=x
            dfs(i,x)

for _ in range(q):
    r=[1]*(n+1)
    p,x=map(int,input().split())
    dfs(p,x)


print(*c[1:])


Fixed submission:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)

n,q=map(int,input().split())
g=[[] for _ in range(n+1)]

for _ in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
c=[0]*(n+1)
que=[1]
done=[0]*(n+1)
done[1]=1
for _ in range(q):
    p,x=map(int,input().split())
    c[p]+=x
while que:
    d=que.pop()
    for node in g[d]:
        if not done[node]:
            c[node]+=c[d]
            que.append(node)
            done[node]+=1
print(*c[1:])
Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())
n=len(s)
mod=10**9+7
dp=[[0]*13 for j in range(100005)]
dp[0][0]=1
for i in range(n):
    if s[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13]+=dp[i][k]
        for j in range(13):
            dp[i+1][j]%=mod
    else:
        for k in range(13):
            dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]
        for j in range(13):
            dp[i+1][j]%=mod
print(dp[n][5])


Fixed submission:
s=list(input())
n=len(s)
mod=10**9+7
dp=[[0]*13 for j in range(100005)]
dp[0][0]=1
for i in range(n):
    if s[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13]+=dp[i][k]
        for j in range(13):
            dp[i+1][j]%=mod
    else:
        for k in range(13):
            dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]
        for j in range(13):
            dp[i+1][j]%=mod
print(dp[n][5])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=[int(input())]

for i in range(n-1):
    a=int(input())
    f=True
    for i in range(len(l)):
        if l[i]<a:
            l[i]=a
            f=False
            break
    if f:
        l.append(a)
print(len(l))


Fixed submission:
import sys,bisect
input=sys.stdin.readline
n=int(input())

a=[int(input()) for _ in range(n)]
a.reverse()

dp=[float("inf")]*(n+1)
for b in a:
    idx=bisect.bisect_right(dp,b)
    dp[idx]=b

ans=bisect.bisect_left(dp,float("inf"))

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
l=[int(input())]

for i in range(n-1):
    a=int(input())
    f=True
    for i in range(len(l)):
        if l[i]<a:
            l[i]=a
            f=False
            break
    if f:
        l.append(a)
print(len(l))


Fixed submission:
import sys,bisect
input=sys.stdin.readline
n=int(input())

a=[int(input()) for _ in range(n)]
a.reverse()

dp=[float("inf")]*(n+1)
for b in a:
    idx=bisect.bisect_right(dp,b)
    dp[idx]=b

ans=bisect.bisect_left(dp,float("inf"))

print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
da={}
db={}
xy=[]
for _ in range(n):
    xy.append(list(map(int,input().split())))

for i in range(n):
    usedx=[]
    usedy=[]
    x1,y1=xy[i]
    for j in range(n):
        if i==j:
            continue
        x,y=xy[j]

        if x-x1 not in usedx and x-x1!=0:
            if x-x1 not in da:
                da[x-x1]=1
            else:
                da[x-x1]=da[x-x1]+1
            usedx.append(x-x1)

        if y-y1 not in usedy and y-y1!=0:
            if y-y1 not in db:
                db[y-y1]=1
            else:
                db[y-y1]=db[y-y1]+1
            usedy.append(y-y1)
print(n-min(max(da.values()),max(db.values())))


Fixed submission:
n=int(input())
xy=[tuple(map(int,input().split())) for _ in range(n)]
pq=[]
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        sx,sy=xy[i]
        gx,gy=xy[j]
        pq.append((gx-sx,gy-sy))


se=set(xy)

ans=n
for p,q in pq:
    now=0
    for x,y in xy:
        if (x+p,y+q) not in se:
            now+=1
    ans=min(ans,now)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
l=[[0]*w for _ in range(h)]
r=[[0]*w for _ in range(h)]
u=[[0]*w for _ in range(h)]
d=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        if j==0:
            l[i][j]=1
        else:
            l[i][j]=l[i][j-1]+1
        if j==w-1:
            r[i][j]=1
        else:
            r[i][j]=r[i][j+1]+1
        if i==0:
            u[i][j]=1
        else:
            u[i][j]=u[i-1][j]+1
for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if s[i][j]=="#":
            continue
        if j==w-1:
            r[i][j]=1
        else:
            r[i][j]=r[i][j+1]+1
        if i==h-1:
            d[i][j]=1
        else:
            d[i][j]=d[i+1][j]+1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)
print(ans)


Fixed submission:
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
l=[[0]*w for _ in range(h)]
r=[[0]*w for _ in range(h)]
u=[[0]*w for _ in range(h)]
d=[[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        if j==0:
            l[i][j]=1
        else:
            l[i][j]=l[i][j-1]+1
        if j==w-1:
            r[i][j]=1
        else:
            r[i][j]=r[i][j+1]+1
        if i==0:
            u[i][j]=1
        else:
            u[i][j]=u[i-1][j]+1
for i in range(h-1,-1,-1):
    for j in range(w-1,-1,-1):
        if s[i][j]=="#":
            continue
        if j==w-1:
            r[i][j]=1
        else:
            r[i][j]=r[i][j+1]+1
        if i==h-1:
            d[i][j]=1
        else:
            d[i][j]=d[i+1][j]+1
ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)
print(ans)
Buggy python submission (verdict: Runtime Error):
n,a,b,c,d=map(int,input().split())
s=list(input())
fa=True
fb=True
ff=False
for i in range(a,c-1):
    if s[i]=="#" and s[i+1]=="#":
        fa=False
for i in range(b,d-1):
    if s[i]=="#" and s[i+1]=="#":
        fb=False
if c>d:
    for i in range(a,d):
        if s[i]=="." and s[i+1]=="." and s[i+2]==".":
            ff=True
if c<d:
    if fa and fb:
        print("Yes")
    else:
        print("No")
else:
    if fa and fb and ff:
        print("Yes")
    else:
        print("No")


Fixed submission:
n,a,b,c,d=map(int,input().split())
s=list(input())
fa=True
fb=True
ff=False
for i in range(a,c-1):
    if s[i]=="#" and s[i+1]=="#":
        fa=False
for i in range(b,d-1):
    if s[i]=="#" and s[i+1]=="#":
        fb=False
if c>d:
    for i in range(b-2,d-1):
        if s[i]=="." and s[i+1]=="." and s[i+2]==".":
            ff=True
if c<d:
    if fa and fb:
        print("Yes")
    else:
        print("No")
else:
    if fa and fb and ff:
        print("Yes")
    else:
        print("No")

Buggy python submission (verdict: Runtime Error):
n,a,b,c,d=map(int,input().split())
s=list(input())
fa=True
fb=True
ff=False
for i in range(a,c-1):
    if s[i]=="#" and s[i+1]=="#":
        fa=False
for i in range(b,d-1):
    if s[i]=="#" and s[i+1]=="#":
        fb=False

for i in range(a,d-1):
    if s[i]=="." and s[i+1]=="." and s[i+2]==".":
        ff=True
if c<d:
    if fa and fb:
        print("Yes")
    else:
        print("No")
else:
    if fa and fb and ff:
        print("Yes")
    else:
        print("No")


Fixed submission:
n,a,b,c,d=map(int,input().split())
s=list(input())
fa=True
fb=True
ff=False
for i in range(a,c-1):
    if s[i]=="#" and s[i+1]=="#":
        fa=False
for i in range(b,d-1):
    if s[i]=="#" and s[i+1]=="#":
        fb=False
if c>d:
    for i in range(b-2,d-1):
        if s[i]=="." and s[i+1]=="." and s[i+2]==".":
            ff=True
if c<d:
    if fa and fb:
        print("Yes")
    else:
        print("No")
else:
    if fa and fb and ff:
        print("Yes")
    else:
        print("No")
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
ans=0
import math
for i in range(1,n+1):
    x=math.log2(k)-math.log2(i)
    if x<=0:
        ans+=1
        continue
    if x.is_integer():
        ans+=1/(2**x)
    else:
        ans+=1/(2**(int(x)+1))
print(ans/n)


Fixed submission:
n,k=map(int,input().split())
cou=0
for i in range(1,min(n+1,k)):
    for j in range(20):
        if i*(2**j)>=k:
            cou+=(1/n)*(1/2)**j
            break
if n>=k:
    cou+=(n+1-k)/n
print(cou)
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,n=map(int,input().split())
c=0
for i in range(n+1):
    r=R*i
    if r>n:
        break
    for j in range(n+1):
        g=G*j
        if r+g>n:
            break
        b=n-r-g
        if b%B==0:
            c+=1
print(c)


Fixed submission:
R,G,B,n=map(int,input().split())
def cou(R,G,B,n):
    c=0
    for i in range(n+1):
        r=R*i
        if r>n:
            break
        for j in range(n+1):
            g=G*j
            if r+g>n:
                break
            b=n-r-g
            if b%B==0:
                c+=1
    return c
print(cou(R,G,B,n))
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(a):
    if a[i]<0:
        c+=1
        a[i]=-1*a[i]
aa=list(map(abs,a))
if c%2==0:
    print(sum(aa))
else:
    print(sum(aa)-2*min(aa))


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(n):
    if a[i]<0:
        c+=1
        a[i]=-1*a[i]
aa=list(map(abs,a))
if c%2==0:
    print(sum(aa))
else:
    print(sum(aa)-2*min(aa))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
a.append(0)

x=[0]*(n+1)
for i in range(n-1):
    if a[i]<0:
        a[i]=-1*a[i]
        a[i+1]=-1*a[i+1]
        x[i+1]=max(sum(a),x[i])


print(max(max(x),sum(a)))


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(n):
    if a[i]<0:
        c+=1
        a[i]=-1*a[i]
aa=list(map(abs,a))
if c%2==0:
    print(sum(aa))
else:
    print(sum(aa)-2*min(aa))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
aa=list(map(int,input().split()))
aa.append(0)
aaa=tuple(aa)
a=list(aaa)
x=[0]*(n+1)
for i in range(n-1):
    if a[i]<0:
        a[i]=-1*a[i]
        a[i+1]=-1*a[i+1]
        x[i+1]=max(sum(a),x[i])


print(max(max(x),sum(aa)))


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(n):
    if a[i]<0:
        c+=1
        a[i]=-1*a[i]
aa=list(map(abs,a))
if c%2==0:
    print(sum(aa))
else:
    print(sum(aa)-2*min(aa))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
aa=list(map(int,input().split()))
aa.append(0)
aaa=tuple(aa)
a=list(aaa)
x=[0]*(n+1)
for i in range(n-1):
    if a[i]<0:
        a[i]=-1*a[i]
        a[i+1]=-1*a[i+1]
        x[i+1]=max(sum(a),x[i])
b=list(aaa)
y=[0]*(n+1)
for i in range(n,0,-1):
    if b[i]<0:
        b[i]=-1*b[i]
        b[i-1]=-1*b[i-1]
        y[i+1]=max(sum(b),y[i])

print(max(max(x),max(y),sum(aa)))

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(n):
    if a[i]<0:
        c+=1
        a[i]=-1*a[i]
aa=list(map(abs,a))
if c%2==0:
    print(sum(aa))
else:
    print(sum(aa)-2*min(aa))

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

print(max(sum(a),sum(b))


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
c=0
for i in range(n):
    if a[i]<0:
        c+=1
        a[i]=-1*a[i]
aa=list(map(abs,a))
if c%2==0:
    print(sum(aa))
else:
    print(sum(aa)-2*min(aa))
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=list(input())

b2=0
h2=0
for i in range(len(s)-1,-1,-1):
    if s[i]=="#" and h2!=0:
        b2+=1
    if s[i]==".":
        h2+=1
print(b2)


Fixed submission:
a,b,c=map(int,input().split())
if (c>a and c<b) or (c<a and c>b):
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if a>b:
    m+=a
    a=a-1
m+=max(a,b)
print(m)

Fixed submission:
a,b=map(int,input().split())
m=0
if a>b:
    m+=a
    a=a-1
else:
    m+=b
    b=b-1
m+=max(a,b)
print(m)
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
s=input()
from collections import deque
l=deque()
c=1
for i in range(1,n):
    if s[i]!=s[i-1]:
        l.append([s[i-1],c])
        c=1
    else:
        c+=1
l.append([s[-1],c])
if l[0][0]=="1":
    a,c=l.popleft()
    l[0][1]+=c
if l[-1][0]=="1":
    a,c=l.pop()
    l[-1][1]+=c

ll=[]
for i in range(len(l)):
    ll.append(l[i][1])

ans=0
for i in range(len(ll)-2*k+1):
    ans=max(ans,sum(ll[i:i+2*k]))
print(ans)


Fixed submission:
n,k=map(int,input().split())
s=input()
wa=[]
now=1
cnt=0
for i in range(n):
    if s[i]==str(0+now):
        cnt+=1
    else:
        wa.append(cnt)
        now=1-now
        cnt=1
if cnt!=0:
    wa.append(cnt)

if len(wa)%2==0:
    wa.append(0)

add=2*k+1
ans=0

left=0
right=0
tmp=0
for i in range(0,len(wa),2):
    nextleft=i
    nextright=min(i+add, len(wa))

    while nextleft > left:
        tmp-=wa[left]
        left+=1
    while nextright > right:
        tmp+=wa[right]
        right+=1

    ans=max(tmp,ans)
print(ans)
Buggy python submission (verdict: Runtime Error):
b=input()
if b="A":
    print("T")
elif b="T":
    print("T")
elif b="C":
    print("G")
else:
    print("C")
    

Fixed submission:
b=input()
if b=="A":
    print("T")
elif b=="T":
    print("A")
elif b=="C":
    print("G")
else:
    print("C")
Buggy python submission (verdict: Runtime Error):
n=int(input())
mod=10**9+7
memo=[[] for _ in range(n+1)]
def ok(last4):
    for i in range(4):
        t=list(last4)
        if i>=1:
            t[i-1],t[i]=t[i],t[i-1]
        if "".join(t).count("AGC")>=1:
            return False
    return True

def dfs(cur,last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur==n:
        return 1
    ret=0
    for c in "ACGT":
        ret=(ret+dfs(cur+1,last3[1:]+c))%mod
    memo[cur][last3]=ret
    return ret
print(dfs(0,"TTT"))


Fixed submission:
n=int(input())
mod=10**9+7
memo=[{} for _ in range(n+1)]
def ok(last4):
    for i in range(4):
        t=list(last4)
        if i>=1:
            t[i-1],t[i]=t[i],t[i-1]
        if "".join(t).count("AGC")>=1:
            return False
    return True

def dfs(cur,last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur==n:
        return 1
    ret=0
    for c in "ACGT":
        if ok(last3+c):
            ret=(ret+dfs(cur+1,last3[1:]+c))%mod
    memo[cur][last3]=ret
    return ret
dfs(0,"TTT")
print(memo[0]["TTT"])
Buggy python submission (verdict: Runtime Error):
nn=int(input())
import sys
input=sys.stdin.readline
cc=[int(input()) for _ in range(n)]
c=[cc[0]]
for i in range(1,nn):
    if cc[i]!=c[-1]:
        c.append(cc[i])
n=len(c)
mod=10**9+7
dp=[0]*(n+1)
sm=[0]*(max(c)+1)
dp[0]=1
for i in range(n):
    x=c[i]
    dp[i+1]+=sm[x]+dp[i]
    sm[x]+=dp[i]
    dp[i]%=mod
    dp[i+1]%=mod
print(dp[n])


Fixed submission:
nn=int(input())
import sys
input=sys.stdin.readline
cc=[int(input()) for _ in range(nn)]
c=[cc[0]]
for i in range(1,nn):
    if cc[i]!=c[-1]:
        c.append(cc[i])
n=len(c)
mod=10**9+7
dp=[0]*(n+1)
sm=[0]*(max(c)+1)
dp[0]=1
for i in range(n):
    x=c[i]
    dp[i+1]+=sm[x]+dp[i]
    sm[x]+=dp[i]
    dp[i]%=mod
    dp[i+1]%=mod
print(dp[n])

Buggy python submission (verdict: Runtime Error):
n=int(input())
c=[int(input()) for _ in range(n)]
c.insert(0,0)
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
place=[[] for _ in range(n+1)]

for i in range(n+1):
    place[c[i]].append(i)

import bisect
for i in range(1,n+1):
    dp[i]+=dp[i-1]
    col=c[i-1]
    it=bisect.bisect_left(place[col],i-1)
    if it>0:
        j=place[col][it-1]
        if i-1-j>1:
            dp[i]+=dp[j+1]
print(dp[n])


Fixed submission:
nn=int(input())
import sys
input=sys.stdin.readline
cc=[int(input()) for _ in range(nn)]
c=[cc[0]]
for i in range(1,nn):
    if cc[i]!=c[-1]:
        c.append(cc[i])
n=len(c)
mod=10**9+7
dp=[0]*(n+1)
sm=[0]*(max(c)+1)
dp[0]=1
for i in range(n):
    x=c[i]
    dp[i+1]+=sm[x]+dp[i]
    sm[x]+=dp[i]
    dp[i]%=mod
    dp[i+1]%=mod
print(dp[n])

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
n=int(input())
c=[int(input()) for _ in range(n)]
#g=[[]for _ in range(2*(10**5)+1)]
g=[[] for _ in range(10)]


for i in range(n):
    g[c[i]].append(i)

ans=1
for i in range(len(g)):
    if not g[i]:
        continue
    new=[]
    now=g[i][0]
    cnt=1
    m=1
    for j in range(1,len(g[i])):
        m+=1
        if now+1==g[i][j]:
            cnt+=1
            now+=1
        else:
            now=g[i][j]
            new.append(cnt)
            cnt=1
    new.append(cnt)
    ans2=m*(m-1)//2
    for k in new:
        ans2-=k*(k-1)//2
    ans+=ans2

print(ans)


Fixed submission:
nn=int(input())
import sys
input=sys.stdin.readline
cc=[int(input()) for _ in range(nn)]
c=[cc[0]]
for i in range(1,nn):
    if cc[i]!=c[-1]:
        c.append(cc[i])
n=len(c)
mod=10**9+7
dp=[0]*(n+1)
sm=[0]*(max(c)+1)
dp[0]=1
for i in range(n):
    x=c[i]
    dp[i+1]+=sm[x]+dp[i]
    sm[x]+=dp[i]
    dp[i]%=mod
    dp[i+1]%=mod
print(dp[n])
Buggy python submission (verdict: Runtime Error):
s=(H-h)*(W-w)
print(s)


Fixed submission:
H,W=map(int,input().split())
h,w=map(int,input().split())

print((H-h)*(W-w))

Buggy python submission (verdict: Runtime Error):
int(input(H W h w))

s=(H-h)*(W-w)
print(s)


Fixed submission:
H,W=map(int,input().split())
h,w=map(int,input().split())

print((H-h)*(W-w))

Buggy python submission (verdict: Runtime Error):
int(input(H,W,h,w))

s=(H-h)*(W-w)
print(s)


Fixed submission:
H,W=map(int,input().split())
h,w=map(int,input().split())

print((H-h)*(W-w))