Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def main():
    input = sys.stdin.readline
    N,C=map(int, input().split())
    D=[tuple(map(int, input().split())) for _ in range(C)]
    c=[tuple(map(int, input().split())) for _ in range(N)]

    ans = 10**10
    from itertools import permutations
    for colors in permutations(range(C), 3):
        tmp = 0
        for i in range(N):
            for j in range(N):
                tmp += D[c[i][j]-1][colors[(i+j)%3]]
        ans = min(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
N,C=map(int, input().split())
D=[list(map(int, input().split())) for _ in range(C)]
c=[list(map(int, input().split())) for _ in range(N)]

d = [[] for _ in range(3)]

for color in range(1,C+1):
    t = [0]*3
    for i in range(N):
        for j in range(N):
            if c[i][j] != color:
                t[(i+j)%3] += D[c[i][j]-1][color-1]
    for k in range(3):
        d[k].append((color, t[k]))

for k in range(3):
    d[k].sort(key=lambda x:x[1])

ans = 10**9
for i in range(3):
    for j in range(3):
        for k in range(3):
            if len({d[0][i][0], d[1][j][0], d[2][k][0]}) != 3: continue
            ans = min(ans, d[0][i][1] + d[1][j][1] + d[2][k][1])
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
def main():
    input = sys.stdin.readline
    N,K,Q=map(int, input().split())
    *A,=map(int, input().split())

    ans=10**10
    from heapq import heappop, heappush
    A.append(-1)
    for y in A:
        if y==-1: break
        c=[]
        t=[]
        for a in A:
            if a >= y:
                heappush(t, a)
            else:
                for _ in range(len(t)-(K-1)):
                    heappush(c, heappop(t))
                t.clear()
        if len(c) < Q: continue
        x=[heappop(c) for _ in range(Q)][-1]
        ans = min(ans, x-y)
    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:
N,K,Q=map(int, input().split())
*A,=map(int, input().split())

import heapq
ans = 10**10
A.append(-1)
for y in A:
    if y==-1: break
    p,q=[],[]
    for a in A:
        if a >= y:
            heapq.heappush(p, a)
        else:
            for i in range(max(0,len(p)-(K-1))):
                heapq.heappush(q, heapq.heappop(p))
            p=[]
    if len(q) < Q: continue
    x = -1
    for i in range(Q):
        x = heapq.heappop(q)
    ans = min(ans, x-y)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
K = int(input())

D = {c:[] for c in "abcdefghijklmnopqrstuvwxyz"}
for i,c in enumerate(s):
    D[c].append(i)

ans = []
for I in D.values():
    t = []
    for l in range(1,len(s)+1):
        for i in I:
            if i+l < len(s)+1:
                t.append(s[i:i+l])
    ans += sorted(list(set(t)))
    if len(ans)>=K:
        break
print(ans[K-1])


Fixed submission:
s = input()
K = int(input())

D = {c:[] for c in "abcdefghijklmnopqrstuvwxyz"}
for i,c in enumerate(s):
    D[c].append(i)

ans = []
for I in D.values():
    t = []
    for l in range(1,K+1):
        for i in I:
            if i+l < len(s)+1:
                t.append(s[i:i+l])
    ans += sorted(list(set(t)))
    if len(ans)>=K:
        break
print(ans[K-1])
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
n = [ord(c)-ord('a') for c in S]

if S == 'zyxwvutsrqponmlkjihgfedcba':
    print(-1)
    exit()

def next(x):
    if len(x) < 26:
        for c in range(26):
            if not c in x:
                x.append(c)
                return x
    k = 0
    flag = True
    x[-1] += 1
    c = 0
    for i in range(len(x)):
        x[-1-i] += k
        if x[-1-i] >= 26:
            if flag: c += 1
            else: x[-1-i] -= 26
            k = 1
        else:
            flag = False
            k = 0
    if k == 1: return None
    if c: return x[:-c]
    return x

def check(x):
    c = [False]*26
    for i in x:
        if x == -1: continue
        if c[i]: return False
        c[i] = True
    return True

while True:
    n = next(n)
    if n == None:
        print(-1)
        exit()
    if check(n): break

ans = ""
for i in n:
    if i != -1: ans += chr(ord('a') + i)
print(ans)

Fixed submission:
S = input()
n = len(S)

import string
def f(x, mn=None):
    for c in string.ascii_lowercase:
        if c in x: continue
        if mn and c <= mn: continue
        return c
    return None

if n < 26:
    print(S + f(S))
    exit()

i = n-2
while i >= 0:
    if S[i] < S[i+1]: break
    i -= 1
else:
    print(-1)
    exit()

t = S[:i]
print(t + f(t, S[i]))
Buggy python submission (verdict: Runtime Error):
N,H=map(int,input().split())
iAB=[]
a_max=(0,0,0)
for i in range(N):
    a,b=map(int,input().split())
    iAB.append((i,a,b))
    if a_max[1]<a or (a_max[1]==a and a_max[2]>b):
        a_max=(i,a,b)

#最大ダメージの刀以外を振る意味はない
#振った場合の最大ダメージを超えるダメージを投げて出せる刀はどんどん投げる
#最大ダメージの刀を投げて1撃で倒せる状態なら投げる

#投げダメージの降順でソート
iAB.sort(key=lambda x:x[2], reverse=True)

ans=0 #攻撃回数
throw_idx=0 if a_max[0]!=iAB[0][0] else 1 #投げチェックindex

#倒すまでループ
#print(a_max,throw_idx)###########
while H>0:
    if a_max[2]>=H:
        #最大ダメージの刀を投げて1撃で倒せる状態なら投げて終わり
        #print("{0}を最後に投げてHPは{1}になった".format(a_max,H-a_max[2]))
        ans+=1
        break
    if throw_idx<N and iAB[throw_idx][2]>a_max[1]:
        #最大じゃない刀を投げる
        H-=iAB[throw_idx][2]
        #print("{0}を投げてHPは{1}になった".format(iAB[throw_idx],H))
        throw_idx+=1
        throw_idx+=1 if iAB[throw_idx][0]==a_max[0] else 0
        ans+=1
        continue
    #もう投げられるものがない
    #振りまくる(投げ分のHPは残す)
    furi=(H-a_max[2])//a_max[1] +(1 if (H-a_max[2])%a_max[1] else 0)
    #print("{0}を{1}回振ってHPは{2}になった".format(a_max,furi,furi*a_max[1]))
    ans+=furi
    H-=furi*a_max[1]
    if a_max[1]>=H:
        #1回振って倒せるなら振って終わり
        #print("{0}を最後に1回振ってHPは{1}になった".format(a_max,H-a_max[1]))
        ans+=1
        break

print(ans)

Fixed submission:
N,H=map(int,input().split())
iAB=[]
a_max=(0,0,0)
for i in range(N):
    a,b=map(int,input().split())
    iAB.append((i,a,b))
    if a_max[1]<a or (a_max[1]==a and a_max[2]>b):
        a_max=(i,a,b)

#最大ダメージの刀以外を振る意味はない
#振った場合の最大ダメージを超えるダメージを投げて出せる刀はどんどん投げる
#最大ダメージの刀を投げて1撃で倒せる状態なら投げる

#投げダメージの降順でソート
iAB.sort(key=lambda x:x[2], reverse=True)

ans=0 #攻撃回数
throw_idx=0 if a_max[0]!=iAB[0][0] else 1 #投げチェックindex

#倒すまでループ
#print(a_max,throw_idx)###########
while H>0:
    if a_max[2]>=H:
        #最大ダメージの刀を投げて1撃で倒せる状態なら投げて終わり
        #print("{0}を最後に投げてHPは{1}になった".format(a_max,H-a_max[2]))
        ans+=1
        break
    if throw_idx<N and iAB[throw_idx][2]>a_max[1]:
        #最大じゃない刀を投げる
        H-=iAB[throw_idx][2]
        #print("{0}を投げてHPは{1}になった".format(iAB[throw_idx],H))
        throw_idx+=1
        throw_idx+=1 if throw_idx<N and iAB[throw_idx][0]==a_max[0] else 0
        ans+=1
        continue
    #もう投げられるものがない
    #振りまくる(投げ分のHPは残す)
    furi=(H-a_max[2])//a_max[1] +(1 if (H-a_max[2])%a_max[1] else 0)
    #print("{0}を{1}回振ってHPは{2}になった".format(a_max,furi,furi*a_max[1]))
    ans+=furi
    H-=furi*a_max[1]
    if a_max[1]>=H:
        #1回振って倒せるなら振って終わり
        #print("{0}を最後に1回振ってHPは{1}になった".format(a_max,H-a_max[1]))
        ans+=1
        break

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
Q=int(input())
queries=[tuple(map(int,input().split())) for _ in range(Q)]

memo=[-1]*(10**5+1)
memo[1]=0
def is_prime1(n):
    if memo[n]!=-1:
        return(memo[n]==1)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            memo[n]=0
            return False
    memo[n]=1
    return True

p=[True]*(10**5+1)
def is_prime2(n):
    return(p[n])

def sleve():
    p[0]=False
    p[1]=False
    primes=[]
    for i in range(2,10**5+1):
        if p[i]:
            primes.append(i)
            for j in range(2*i, 10**5+1, i):
                p[j]=False

sleve()
is_prime=is_prime2
for l,r in queries:
    ans=0
    for n in range(l,r+1):
        if n&1:
            if is_prime(n) and is_prime((n+1)//2):
                ans+=1
    print(ans)


Fixed submission:
Q=int(input())
queries=[tuple(map(int,input().split())) for _ in range(Q)]

#エラトステネスの篩
p=[True]*(10**5+1)
p[0]=False
p[1]=False
for i in range(2,10**5+1):
    if p[i]:
        for j in range(2*i, 10**5+1, i):
            p[j]=False

#like2017[n]=n以下の「2017に似た数」の数
like2017=[0]*(10**5+1)
for i in range(1,10**5+1):
    like2017[i]=like2017[i-1]+(1 if i&1 and p[i] and p[(i+1)//2] else 0)

for l,r in queries:
    print(like2017[r]-like2017[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
Q=int(input())
queries=[tuple(map(int,input().split())) for _ in range(Q)]

memo=[-1]*(10**5+1)
memo[1]=0
def is_prime(n):
    if memo[n]!=-1:
        return(memo[n]==1)
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            memo[n]=0
            return False
    memo[n]=1
    return True

for l,r in queries:
    ans=0
    for n in range(l,r+1):
        if n&1:
            if is_prime(n) and is_prime((n+1)//2):
                ans+=1
    print(ans)


Fixed submission:
Q=int(input())
queries=[tuple(map(int,input().split())) for _ in range(Q)]

#エラトステネスの篩
p=[True]*(10**5+1)
p[0]=False
p[1]=False
for i in range(2,10**5+1):
    if p[i]:
        for j in range(2*i, 10**5+1, i):
            p[j]=False

#like2017[n]=n以下の「2017に似た数」の数
like2017=[0]*(10**5+1)
for i in range(1,10**5+1):
    like2017[i]=like2017[i-1]+(1 if i&1 and p[i] and p[(i+1)//2] else 0)

for l,r in queries:
    print(like2017[r]-like2017[l-1])
Buggy python submission (verdict: Runtime Error):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import groupby
import sys
def main(s, x, y):
    g = [x, y]
    o = [[], []]

    direction = count = 0
    first = True
    for c in s:
        if c == 'T':
            if first:
                g[0] -= count
                first = False
            elif count > 0:
                o[direction].append(count)
            count = 0
            direction ^= 1
        else:
            count += 1
    if first:
        g[0] -= count
    elif count > 0:
        o[direction].append(count)

    for d in range(2):
        l = o[d]
        M = sum(l)
        M2 = M * 2
        if abs(g[d]) > M:
            print('No')
            return
        pre = [False] * (M2 + 1)
        pre[M] = True
        for i, v in enumerate(l):
            dp = [False] * (M2 + 1)
            for a in range(M2 + 1):
                if pre[a] == False: continue
                if a >= v:
                    dp[a - v] = True
                if a + v <= M2:
                    dp[a + v] = True
            pre = dp
        if dp[g[d] + M] == False:
            print('No')
            return
    print('Yes')

if __name__ == '__main__':
    input = sys.stdin.readline
    s = input().rstrip()
    x, y = map(int, input().split())
    main(s, x, y)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import groupby
import sys
def main(s, x, y):
    g = [x, y]
    o = [[], []]

    direction = count = 0
    first = True
    for c in s:
        if c == 'T':
            if first:
                g[0] -= count
                first = False
            elif count > 0:
                o[direction].append(count)
            count = 0
            direction ^= 1
        else:
            count += 1
    if first:
        g[0] -= count
    elif count > 0:
        o[direction].append(count)

    for d in range(2):
        l = o[d]
        M = sum(l)
        M2 = M * 2
        if abs(g[d]) > M:
            print('No')
            return
        pre = [False] * (M2 + 1)
        pre[M] = True
        for i, v in enumerate(l):
            dp = [False] * (M2 + 1)
            for a in range(M2 + 1):
                if pre[a] == False: continue
                if a >= v:
                    dp[a - v] = True
                if a + v <= M2:
                    dp[a + v] = True
            pre = dp
        if pre[g[d] + M] == False:
            print('No')
            return
    print('Yes')

if __name__ == '__main__':
    input = sys.stdin.readline
    s = input().rstrip()
    x, y = map(int, input().split())
    main(s, x, y)
Buggy python submission (verdict: Runtime Error):
import sys
import io, os
def main():
    input = sys.stdin.readline
    inputb = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    N=int(input())
    A=[int(input()) for _ in range(N)]
    from collections import Counter
    C=Counter(A)
    ans=0
    for v in C.values():
        if v&1: ans+=1
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    A=[int(input()) for _ in range(N)]
    from collections import Counter
    C=Counter(A)
    ans=0
    for v in C.values():
        if v&1: ans+=1
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
N,M,R=map(int, input().split())
r=map(lambda x:int(x)-1, input().split())
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for p in itertools.permutations(range(R)):
    t=0
    rp=[r[i] for i in p]
    for i in range(R-1):
        t+=dp[rp[i]][rp[i+1]]
    ans=min(ans,t)
print(ans)

Fixed submission:
N,M,R=map(int, input().split())
r=list(map(int, input().split()))
dp=[[10**9]*N for _ in range(N)]
for _ in range(M):
    A,B,C=map(int, input().split())
    A-=1
    B-=1
    dp[A][B]=C
    dp[B][A]=C
for z in range(N):
    for x in range(N):
        for y in range(N):
            dp[x][y]=min(dp[x][y], dp[x][z]+dp[z][y])

import itertools
ans=10**9
for p in itertools.permutations(range(R)):
    t=0
    rp=[r[i] for i in p]
    for i in range(R-1):
        t+=dp[rp[i]-1][rp[i+1]-1]
    ans=min(ans,t)
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
P=[1]+list(map(int,input().split()))

ans=0
for i in range(1,N+1):
    if P[i]==i:
        if i+1==P[i+1] or i==1:
            P[i+1],P[i]=P[i],P[i+1]
            ans+=1
        else:
            P[i-1],P[i]=P[i],P[i-1]
            ans+=1
print(ans)

Fixed submission:
N=int(input())
P=[1]+list(map(int,input().split()))

ans=0
for i in range(1,N+1):
    if P[i]==i:
        if (i<N and i+1==P[i+1]) or i==1:
            P[i+1],P[i]=P[i],P[i+1]
            ans+=1
        else:
            P[i-1],P[i]=P[i],P[i-1]
            ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
from bisect import bisect_left
from itertools import accumulate
a = map(int, input().split())
A = list(accumulate(a))
m = A[-1]//2
i = bisect_left(A, m)
ans1 = abs(A[-1] - A[i] - A[i])
ans2 = abs(A[-1] - A[i-1] - A[i-1]) if i >= 1 else ans1
print(min(ans1,ans2))


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
a = sum(A) - A[0]
s = A[0]
ans = abs(s - a)
for i in range(1,N-1):
    a -= A[i]
    s += A[i]
    ans = min(ans, abs(s - a))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import defaultdict
import sys
N_MAX = 100
W_MAX = 10**9
V_MAX = 10**7
INF = 10**10
def main(N, W, items):
    dp = defaultdict(lambda: INF)
    dp[0] = 0
    for i in range(N):
        iw, iv = items[i]
        for v, w in list(dp.items()):
            if w + iw <= W:
                dp[v + iv] = min(dp[v + iv], w + iw)
    print(max(dp.keys()))

if __name__ == '__main__':
    input = sys.stdin.readline
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, items)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, W, items):
    w1 = items[0][0]
    dp = [[[0] * (3 * N + 1) for _ in range(N + 1)] for __ in range(N + 1)]
    dp[0][0][0] = 0
    for i in range(N):
        iw, iv = items[i]
        iw -= w1
        for j in range(N + 1):
            for w in range(3 * N + 1):
                if j * w1 + w > W: break
                if w >= iw and j >= 1:
                    dp[i + 1][j][w] = max(dp[i][j][w], dp[i][j - 1][w - iw] + iv)
                else:
                    dp[i + 1][j][w] = dp[i][j][w]
    ans = 0
    for j in range(N + 1):
        for w in range(3 * N + 1):
            ans = max(ans, dp[N][j][w])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, items)

Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import defaultdict
import sys
N_MAX = 100
W_MAX = 10**9
V_MAX = 10**7
INF = 10**10
def main(N, W, items):
    dp = defaultdict(lambda: INF)
    dp[0] = 0
    for i in range(N):
        iw, iv = items[i]
        for v, w in list(dp.items()):
            if w + iw <= W:
                dp[v + iv] = min(dp[v + iv], w + iw)
    print(max(dp.keys()))

if __name__ == '__main__':
    input = sys.stdin.readline
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, items)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, W, items):
    w1 = items[0][0]
    dp = [[[0] * (3 * N + 1) for _ in range(N + 1)] for __ in range(N + 1)]
    dp[0][0][0] = 0
    for i in range(N):
        iw, iv = items[i]
        iw -= w1
        for j in range(N + 1):
            for w in range(3 * N + 1):
                if j * w1 + w > W: break
                if w >= iw and j >= 1:
                    dp[i + 1][j][w] = max(dp[i][j][w], dp[i][j - 1][w - iw] + iv)
                else:
                    dp[i + 1][j][w] = dp[i][j][w]
    ans = 0
    for j in range(N + 1):
        for w in range(3 * N + 1):
            ans = max(ans, dp[N][j][w])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, items)
Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, Ma, Mb, ABC):
    ans = 10**10
    for p in range(1, 1 << N):
        ta, tb, tc = 0, 0, 0
        for i in range(N):
            if p & (1 << i):
                a, b, c = ABC[i]
                ta += a
                tb += b
                tc += c
        if ta * Mb == tb * Ma:
            ans = min(ans, tc)
    if ans == 10**10:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, Ma, Mb = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, Ma, Mb, ABC)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
INF = 10**10
def main(N, Ma, Mb, ABC):
    MX = 10 * N
    dp = [[[INF] * (MX + 1) for _ in range(MX + 1)] for __ in range(N + 1)]
    dp[0][0][0] = 0
    for i in range(N):
        ni = i + 1
        ma, mb, mc = ABC[i]
        for na in range(MX + 1):
            a = na - ma
            for nb in range(MX + 1):
                b = nb - mb
                dp[ni][na][nb] = dp[i][na][nb]
                if a >= 0 and b >= 0:
                    dp[ni][na][nb] = min(dp[ni][na][nb], dp[i][a][b] + mc)

    ans = INF
    for a in range(MX + 1):
        for b in range(MX + 1):
            if a == 0 and b == 0: continue
            if a * Mb == b * Ma:
                ans = min(ans, dp[N][a][b])
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, Ma, Mb = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, Ma, Mb, ABC)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
t = a = 0
for i in range(N):
    T,A = map(int, input().split())
    for n in range(1,10**18):
        if t <= T*n and a <= A*n:
            t = T*n
            a = A*n
            break
print(t+a)

Fixed submission:
N = int(input())
t = a = 1
for i in range(N):
    T, A = map(int, input().split())
    tb = (t + T - 1) // T
    ab = (a + A - 1) // A
    b = max(tb, ab)
    t = T * b
    a = A * b
print(t+a)
Buggy python submission (verdict: Time Limit Exceeded):
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    ans = 0
    for i, a in enumerate(A):
        l = r = i
        while l >= 0 and A[l] >= a: l -= 1
        while r < N and A[r] >= a: r += 1
        ans += a * (i - l) * (r - i)
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)


Fixed submission:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    ans = 0
    Ai = [(a, i + 1) for i, a in enumerate(A)]
    Ai.sort(key=lambda x: x[0])
    st = SegmentTree(n=N + 2, f=lambda x, y: x + y)
    st.set_val(0, 1)
    st.set_val(N + 1, 1)
    for a, i in Ai:
        lc = st.query(0, i)
        l = st.bisect_left(lambda x: x < lc)
        r = st.bisect_left(lambda x: x < lc + 1)
        ans += a * (i - l) * (r - i)
        st.set_val(i, 1)
    print(ans)

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i << 1], d[i << 1 | 1])

    def get_val(self, index):
        return self.__d[index + self.__n]

    def set_val(self, index, new_value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == new_value: return
        d[i] = new_value
        i = i >> 1
        while i:
            d[i] = f(d[i << 1], d[i << 1 | 1])
            i = i >> 1

    def modify(self, index, value):
        self.set_val(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l + 1
            if r & 1: ans, r = f(d[r - 1], ans), r - 1
            l, r = l >> 1, r >> 1
        return ans

    def bisect_left(self, func):
        '''func()がFalseになるもっとも左のindexを探す
        '''
        i, n, f, d, v = 1, self.__n, self.__f, self.__d, self.__e()
        i = n
        j = n + n
        while i < j:
            if i & 1:
                nv = f(v, d[i])
                if not func(nv):
                    break
                v = nv
                i += 1
            i >>= 1
            j >>= 1
        while i < n:
            nv = f(v, d[i << 1])
            if func(nv):
                v, i = nv, i << 1 | 1
            else:
                i = i << 1
        return i - n

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
*A,=map(int, input().split())
A=[-1]+A
ans=0
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if A[i]==j and A[j]==i: ans+=1
print(ans)

Fixed submission:
N = int(input())
A = [0] + list(map(int, input().split()))
ans2 = 0
for i in range(N+1):
    if A[A[i]] == i: ans2 += 1
print(ans2//2)