Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())

u = []
for i in range(q):
    u.append(list(map(str,input().split())))

l = ''
r = ''

x = 1
for i in range(q):
    if int(u[i][0]) == 1:
        x = x*(-1)
    else:
        if int(u[i][1])*x == 1 or int(u[i][1])*x == -2:
            l += u[i][2]
        else:
            r += u[i][2]
if x == 1:
    print(l[::-1]+s[::x]+r)
else:
    print(r[::-1]+s[::x]+l)

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

u = []
for i in range(q):
    u.append(list(map(str,input().split())))

from collections import deque
l = deque([])
r = deque([])

x = 1
for i in range(q):
    if int(u[i][0]) == 1:
        x = x*(-1)
    else:
        if int(u[i][1])*x == 1 or int(u[i][1])*x == -2:
            l.append(u[i][2])
        else:
            r.append(u[i][2])
if x == 1:
    print(''.join(l)[::-1]+s[::x]+''.join(r))
else:
    print(''.join(r)[::-1]+s[::x]+''.join(l))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
q = int(input())

u = []
for i in range(q):
    u.append(list(map(str,input().split())))

for i in range(q):
    if int(u[i][0]) == 1:
        s = s[::-1]
    else:
        if int(u[i][1]) == 1:
            s = u[i][2]+s
        else:
            s = s + u[i][2]

print(s)

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

u = []
for i in range(q):
    u.append(list(map(str,input().split())))

from collections import deque
l = deque([])
r = deque([])

x = 1
for i in range(q):
    if int(u[i][0]) == 1:
        x = x*(-1)
    else:
        if int(u[i][1])*x == 1 or int(u[i][1])*x == -2:
            l.append(u[i][2])
        else:
            r.append(u[i][2])
if x == 1:
    print(''.join(l)[::-1]+s[::x]+''.join(r))
else:
    print(''.join(r)[::-1]+s[::x]+''.join(l))
Buggy python submission (verdict: Runtime Error):
n,k,s = map(int,input().split())

u = []
if n == k:
    print(' '.join(str,[s]*n))
else:
    if s%2==0:
        for i in range(k+1):
            u.append(int(s/2))
        for i in range(n-k-1):
            u.append(10**9-1)
    else:
        if s==1:
            for i in range(k):
                u.append(1)
            for i in range(n-k-1):
                u.append(10**9)
        else:
            if k%2==0:
                u.append(int((s-1)/2))
                for i in range(int(k/2)):
                    u.append(int((s+1)/2))
                    u.append(int((s-1)/2))    
                for i in range(n-k+1):
                    u.append(10**9)
            else:
                for i in range(int(k/2)):
                    u.append(int((s+1)/2))
                    u.append(int((s-1)/2))  
                for i in range(n-k+1):
                    u.append(10**9)
print(' '.join(map(str,u)))

Fixed submission:
n,k,s = map(int,input().split())

u = []
if n == k:
    for i in range(n):
        u.append(s)
else:
    if s%2==0:
        for i in range(k+1):
            u.append(int(s/2))
        for i in range(n-k-1):
            u.append(10**9-1)
    else:
        if s==1:
            for i in range(k):
                u.append(1)
            for i in range(n-k):
                u.append(10**9)
        else:
            if k%2==0:
                u.append(int((s-1)/2))
                for i in range(int(k/2)):
                    u.append(int((s+1)/2))
                    u.append(int((s-1)/2))    
                for i in range(n-k-1):
                    u.append(10**9)
            else:
                for i in range(int((k+1)/2)):
                    u.append(int((s+1)/2))
                    u.append(int((s-1)/2))  
                for i in range(n-k-1):
                    u.append(10**9)
print(' '.join(map(str,u)))
Buggy python submission (verdict: Time Limit Exceeded):
(n,m) = tuple(map(int,input().split()))
a = list(map(int,input().split()))

import math
for i in range(m):
    a.sort(reverse = True)
    a[0] = a[0]/2

import math
print(sum(list(map(math.floor,a))))

Fixed submission:
(n,m) = tuple(map(int,input().split()))
b = list(map(int,input().split()))
a = list(map(lambda x:x*(-1),b))

import heapq
heapq.heapify(a)

temp = 0
for i in range(m):
    temp = heapq.heappop(a)
    heapq.heappush(a,temp/2)

import math
c = list(map(lambda x:x*(-1),a))
print(sum(list(map(math.floor,c))))
Buggy python submission (verdict: Runtime Error):
s = int(input())
import math
k = math.floor(s**0.5)
m = 0
if s = 10**18:
    print(10**9,0,0,10**9,0,0)
else:
    if k**2+k < S:
        m = (k+1)**2 -s
        print(k+1,1,m,k+1,0,0)
    else:
        m = k*(k+1)-s
        print(k+1,1,m,k,0,0)

Fixed submission:
s = int(input())
import math
k = math.floor(s**0.5)
m = 0
if s == 10**18:
    print(10**9,0,0,10**9,0,0)
else:
    if k**2+k < s:
        m = (k+1)**2 -s
        print(k+1,1,m,k+1,0,0)
    else:
        m = k*(k+1)-s
        print(k+1,1,m,k,0,0)
Buggy python submission (verdict: Time Limit Exceeded):
h,w = map(int,input().split())
u = [list(input()) for _ in range(h)]
from collections import deque
q = deque([])
dist = [[-1 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if u[i][j]=='#':
            q.append((i,j))
            dist[i][j]=0

while q:
    (i,j) = q.popleft()
    if 0<=i-1<h:
        if u[i-1][j]=='.' and dist[i-1][j]==-1:
            u[i-1][j]='#'
            q.append((i-1,j))
            dist[i-1][j]=dist[i][j]+1
    if 0<=i+1<h:
        if u[i+1][j]=='.' and dist[i+1][j]==-1:
            u[i+1][j]='#'
            q.append((i+1,j))
            dist[i+1][j]=dist[i][j]+1
    if 0<=j-1<w:
        if u[i][j-1]=='.' and dist[i][j-1]==-1:
            u[i][j-1]='#'
            q.append((i,j-1))
            dist[i][j-1]=dist[i][j]+1
    if 0<=j+1<w:
        if u[i][j+1]=='.' and dist[i][j+1]==-1:
            u[i][j+1]='#'
            q.append((i,j+1))
            dist[i][j+1]=dist[i][j]+1

z=[]
for b in dist:
    z.append(max(b))

print(max(z))

Fixed submission:
h,w = map(int,input().split())
u = [list(input()) for _ in range(h)]
from collections import deque
q = deque([])
dist = [[-1 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if u[i][j]=='#':
            q.append((i,j))
            dist[i][j]=0

while q:
    (i,j) = q.popleft()
    if 0<=i-1<h:
        if u[i-1][j]=='.' and dist[i-1][j]==-1:
            u[i-1][j]='#'
            q.append((i-1,j))
            dist[i-1][j]=dist[i][j]+1
    if 0<=i+1<h:
        if u[i+1][j]=='.' and dist[i+1][j]==-1:
            u[i+1][j]='#'
            q.append((i+1,j))
            dist[i+1][j]=dist[i][j]+1
    if 0<=j-1<w:
        if u[i][j-1]=='.' and dist[i][j-1]==-1:
            u[i][j-1]='#'
            q.append((i,j-1))
            dist[i][j-1]=dist[i][j]+1
    if 0<=j+1<w:
        if u[i][j+1]=='.' and dist[i][j+1]==-1:
            u[i][j+1]='#'
            q.append((i,j+1))
            dist[i][j+1]=dist[i][j]+1

z=[]
for b in dist:
    z.append(max(b))

print(max(z))
Buggy python submission (verdict: Runtime Error):
n = int(input())
v = list(map(int,input().split()))

a = [v[2*i] for i in range(int(n/2))]
b = [v[2*i+1] for i in range(int(n/2))]

from collections import Counter

x = Counter(a)
y = Counter(b)
x = list(x.items())
y = list(y.items())
x.sort(reverse=1,key=lambda p: p[1])
y.sort(reverse=1,key=lambda p: p[1])

if x[0][0] != y[0][0]:
    print(n-x[0][1]-y[0][1])
else:
    if x[0][0] == y[0][0]:
        if min(len(x),len(y))>=2:
            print(n-max(x[0][1]+y[1][1],y[0][1]+x[1][1]))
        elif len(x)==2:
            print(n-x[1][1]-y[0][1])
        else:
            print(n-y[1][1]-x[0][1])

Fixed submission:
n = int(input())
v = list(map(int,input().split()))

a = [v[2*i] for i in range(int(n/2))]
b = [v[2*i+1] for i in range(int(n/2))]

from collections import Counter

x = Counter(a)
y = Counter(b)
x = list(x.items())
y = list(y.items())
x.sort(reverse=1,key=lambda p: p[1])
y.sort(reverse=1,key=lambda p: p[1])

if x[0][0] != y[0][0]:
    print(n-x[0][1]-y[0][1])
else:
    if x[0][0] == y[0][0]:
        if min(len(x),len(y))>=2:
            print(n-max(x[0][1]+y[1][1],y[0][1]+x[1][1]))
        elif len(x)==2:
            print(n-x[1][1]-y[0][1])
        elif len(y)==2:
            print(n-y[1][1]-x[0][1])
        else:
            print(int(n/2))

Buggy python submission (verdict: Runtime Error):
n = int(input())
v = list(map(int,input().split()))

a = [v[2*i] for i in range(int(n/2))]
b = [v[2*i+1] for i in range(int(n/2))]

from collections import Counter

x = Counter(a)
y = Counter(b)
x = list(x.items())
y = list(y.items())
x.sort(reverse=1,key=lambda p: p[1])
y.sort(reverse=1,key=lambda p: p[1])

if x[0][0] != y[0][0]:
    print(n-x[0][1]-y[0][1])
else:
    if x[0][0] == y[0][0]:
        print(n-max(x[0][1]+y[1][1],y[0][1]+x[1][1]))
    

Fixed submission:
n = int(input())
v = list(map(int,input().split()))

a = [v[2*i] for i in range(int(n/2))]
b = [v[2*i+1] for i in range(int(n/2))]

from collections import Counter

x = Counter(a)
y = Counter(b)
x = list(x.items())
y = list(y.items())
x.sort(reverse=1,key=lambda p: p[1])
y.sort(reverse=1,key=lambda p: p[1])

if x[0][0] != y[0][0]:
    print(n-x[0][1]-y[0][1])
else:
    if x[0][0] == y[0][0]:
        if min(len(x),len(y))>=2:
            print(n-max(x[0][1]+y[1][1],y[0][1]+x[1][1]))
        elif len(x)==2:
            print(n-x[1][1]-y[0][1])
        elif len(y)==2:
            print(n-y[1][1]-x[0][1])
        else:
            print(int(n/2))
Buggy python submission (verdict: Runtime Error):
n=input()
print((10**n-(2*9**n-8**n))%(10**9+7))

Fixed submission:
n=int(input())
print((10**n-(2*9**n-8**n))%(10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
import collections 
S = [collections.Counter(input()) for i in range(N)]
counter = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]:
            counter += 1
print(counter)




Fixed submission:
N = int(input())
#N = 100000
#S = [input() for i in range(N)]
S = [input() for i in range(N)]
#S = ['zabcdefghi']*100000

#groups = {i: [] for i in range(26)}
sort_str = {}

counter = 0
for i in range(N):
    s = ''.join(sorted(S[i]))
    if s in sort_str:
        counter += sort_str[s]
        sort_str[s] += 1 
    else:
        sort_str[s] = 1
print(counter)
#
#
#    groups[int(s[0], 36) - 10].append(s)
#
#counter = 0
#for group in groups.values():
#    for i in range(len(group)):
#        for j in range(i+1, len(group)):
#            print(i, j)
#            if group[i] == group[j]:
#                counter += 1
#
#print(counter)
#
#
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce
from fractions import gcd
N =  int(input())
A =  list(map(int, (input().split(' '))))


gcds = []
for i in range(len(A)):
    A[:i] + A[i+1:]
    gcds.append(reduce(gcd, A[:i]+A[i+1:]))

print(max(gcds))


Fixed submission:
from functools import reduce
from fractions import gcd
N =  int(input())
A =  list(map(int, (input().split(' '))))

from itertools import accumulate

gcds = []
left_all_gcd = list(accumulate(A, gcd))
right_all_gcd = list(accumulate(A[::-1], gcd))
for i in range(len(A)):
    if i == 0:
        gcds.append(right_all_gcd[-2])
    if i == len(A)-1:
        gcds.append(left_all_gcd[-2])
    else:
        hoge = [left_all_gcd[i-1]] + [right_all_gcd[-i-1]]
        gcds.append(gcd(left_all_gcd[i-1], right_all_gcd[-i-2]))

print(max(gcds))

Buggy python submission (verdict: Runtime Error):
from functools import reduce
from math import gcd
N =  int(input())
A =  list(map(int, (input().split(' '))))


gcds = []
for i in range(len(A)):
    A[:i] + A[i+1:]
    gcds.append(reduce(gcd, A[:i]+A[i+1:]))

print(max(gcds))


Fixed submission:
from functools import reduce
from fractions import gcd
N =  int(input())
A =  list(map(int, (input().split(' '))))

from itertools import accumulate

gcds = []
left_all_gcd = list(accumulate(A, gcd))
right_all_gcd = list(accumulate(A[::-1], gcd))
for i in range(len(A)):
    if i == 0:
        gcds.append(right_all_gcd[-2])
    if i == len(A)-1:
        gcds.append(left_all_gcd[-2])
    else:
        hoge = [left_all_gcd[i-1]] + [right_all_gcd[-i-1]]
        gcds.append(gcd(left_all_gcd[i-1], right_all_gcd[-i-2]))

print(max(gcds))
Buggy python submission (verdict: Time Limit Exceeded):
N, M =  map(int, (input().split(' ')))
A_list = []
B_list = []
money = 0
while len(A_list) < N:
    A, B =  map(int, (input().split(' ')))
    A_list.append(A)
    B_list.append(B)

while True:
    i = A_list.index(min(A_list))
    if B_list[i] < M:
        money += A_list[i] * B_list[i]
        M -= B_list[i]
    else:
        money += A_list[i] * M
        M = 0 
    A_list[i] = 99999999999999999999999999999999999999
    if M == 0:
        print(money)
        exit()

Fixed submission:
N, M =  map(int, (input().split(' ')))
A_B_list = []
money = 0
while len(A_B_list) < N:
    A, B =  map(int, (input().split(' ')))
    A_B_list.append([A, B])
A_B_list = sorted(A_B_list)
    

for A, B in A_B_list:
    if B < M:
        money += A * B
        M -= B
    else:
        money += A * M
        M = 0 
    if M == 0:
        print(money)
        exit()

Buggy python submission (verdict: Time Limit Exceeded):
N, M =  map(int, (input().split(' ')))
A_list = []
B_list = []
money = 0
while len(A_list) < N:
    A, B =  map(int, (input().split(' ')))
    A_list.append(A)
    B_list.append(B)

while True:
    i = A_list.index(min(A_list))
    if B_list[i] < M:
        money += A_list[i] * B_list[i]
        M -= B_list[i]
    else:
        money += A_list[i] * M
        M = 0 
    A_list.pop(i)
    B_list.pop(i)
    if M == 0:
        print(money)
        exit()

Fixed submission:
N, M =  map(int, (input().split(' ')))
A_B_list = []
money = 0
while len(A_B_list) < N:
    A, B =  map(int, (input().split(' ')))
    A_B_list.append([A, B])
A_B_list = sorted(A_B_list)
    

for A, B in A_B_list:
    if B < M:
        money += A * B
        M -= B
    else:
        money += A * M
        M = 0 
    if M == 0:
        print(money)
        exit()
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce
A, B =  map(int, (input().split(' ')))

def xor_sum(A,B):
    bins = [i for i in range(A, B+1)]
    return reduce(xor, bins)
def xor(A,B):
    return A ^ B

print(xor_sum(A,B))

Fixed submission:
from functools import reduce
A, B =  map(int, (input().split(' ')))

def xor_sum(A,B):
        
    if A%2 == 0:
        if B%2 == 1:
            if (B - A + 1) // 2 % 2 == 0:
                hoge = 0
            if (B - A + 1) // 2 % 2 == 1:
                hoge = 1
            print(hoge)
        else:
            if (B - A + 1 - 1) // 2 % 2 == 0:
                hoge = 0
            if (B - A + 1 - 1) // 2 % 2 == 1:
                hoge = 1
            print(hoge ^ B)
    else:
        if B%2 == 0:
            if (B - A + 1 - 2) // 2 % 2 == 0:
                hoge = 0
            if (B - A + 1 - 2) // 2 % 2 == 1:
                hoge = 1
            print((A ^ hoge) ^ B)
        else:
            if (B - A + 1 - 1) // 2 % 2 == 0:
                hoge = 0
            if (B - A + 1 - 1) // 2 % 2 == 1:
                hoge = 1
            print(A ^ hoge)
            
xor_sum(A, B)
Buggy python submission (verdict: Runtime Error):
import bisect
A, B, Q =  map(int, (input().split(' ')))

a_list = [-100001]+[int(input()) for _ in range(A)] + [100001]
b_list = [-100001]+[int(input()) for _ in range(B)] + [100001]
for _ in range(Q):
    x = int(input())
    right_s = abs(x - a_list[bisect.bisect_left(a_list, x)])
    right_t = abs(x - b_list[bisect.bisect_left(b_list, x)])
    left_s = abs(x - a_list[bisect.bisect_right(a_list, x)-1])
    left_t = abs(x - b_list[bisect.bisect_right(b_list, x)-1])
    print(
            min(
                max(left_t, left_s),
                max(right_t, right_s),
                left_t + (left_t + right_s),
                left_s + (left_s + right_t),
                right_t + (right_t + left_s),
                right_s + (right_s + left_t)
            )
    )


Fixed submission:
import bisect
A, B, Q =  map(int, (input().split(' ')))
power = 10**11+1
a_list = [-power]+[int(input()) for _ in range(A)] + [power]
b_list = [-power]+[int(input()) for _ in range(B)] + [power]
for _ in range(Q):
    x = int(input())
    right_s = abs(x - a_list[bisect.bisect_left(a_list, x)])
    right_t = abs(x - b_list[bisect.bisect_left(b_list, x)])
    left_s = abs(x - a_list[bisect.bisect_right(a_list, x)-1])
    left_t = abs(x - b_list[bisect.bisect_right(b_list, x)-1])
    print(
            min(
                max(left_t, left_s),
                max(right_t, right_s),
                left_t + (left_t + right_s),
                left_s + (left_s + right_t),
                right_t + (right_t + left_s),
                right_s + (right_s + left_t)
            )
    )
Buggy python submission (verdict: Runtime Error):
N = int(input())
h_list = list(map(int, input().split(' ')))


def mizuyari(h_list, l, r):
    import pdb;pdb.set_trace()
    num_mizuyari = min(h_list[l:r+1])
    h_list = [h - num_mizuyari if l <= x and x <= r else h for x, h in enumerate(h_list)]
    zero_posi = h_list[l:].index(0) + l
    if l == zero_posi:
        first_non_zero_posi = [x for x, h in enumerate(h_list) if h != 0]
        if not first_non_zero_posi:
            print(sum_mizuyari + num_mizuyari)
            exit()
        l = first_non_zero_posi[0]
        if list(range(l, len(h_list))) == first_non_zero_posi:
            return h_list, num_mizuyari, l, len(h_list)
        zero_posi = h_list[l:].index(0) + l
    new_r = zero_posi - 1
    return h_list, num_mizuyari, l, new_r
l = 0
r = len(h_list) - 1
sum_mizuyari = 0
while True:
    h_list, num_mizuyari, l, r = mizuyari(h_list, l, r)
    sum_mizuyari += num_mizuyari

Fixed submission:
N = int(input())
h_list = list(map(int, input().split(' ')))


def mizuyari(h_list, l, r):
    num_mizuyari = min(h_list[l:r+1])
    h_list = [h - num_mizuyari if l <= x and x <= r else h for x, h in enumerate(h_list)]
    zero_posi = h_list[l:].index(0) + l
    if l == zero_posi:
        first_non_zero_posi = [x for x, h in enumerate(h_list) if h != 0]
        if not first_non_zero_posi:
            print(sum_mizuyari + num_mizuyari)
            exit()
        l = first_non_zero_posi[0]
        if list(range(l, len(h_list))) == first_non_zero_posi:
            return h_list, num_mizuyari, l, len(h_list)
        zero_posi = h_list[l:].index(0) + l
    new_r = zero_posi - 1
    return h_list, num_mizuyari, l, new_r
l = 0
r = len(h_list) - 1
sum_mizuyari = 0
while True:
    h_list, num_mizuyari, l, r = mizuyari(h_list, l, r)
    sum_mizuyari += num_mizuyari
Buggy python submission (verdict: Runtime Error):
import math
import operator
from functools import reduce
N = int(input())
a_list = list(map(int, input().split(' ')))

def lcm_list(numbers):
    return reduce(operator.mul, numbers) // reduce(math.gcd, numbers)

m = lcm_list(a_list) - 1

print(sum([m % a for a in a_list]))


Fixed submission:
import fractions
import operator
from functools import reduce
N = int(input())
a_list = list(map(int, input().split(' ')))

def lcm_list(numbers):
    return reduce(operator.mul, numbers) // reduce(fractions.gcd, numbers)

m = lcm_list(a_list) - 1

print(sum([m % a for a in a_list]))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=1
if 0 in a:
    print(0)
    exit()
for i in a:
    ans*=i
    if ans > (10**18):
        ans=-1
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    b*=a[i]
    if b>10**18:
        print(-1)
        exit()
print(b)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=a[0]
for i in a[1:n]:
    ans*=i
print(-1 if ans >(10**18) else ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    b*=a[i]
    if b>10**18:
        print(-1)
        exit()
print(b)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
ans=1
for i in a:
    ans*=i
if ans > (10**18):
    ans=-1
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b=1
if 0 in a:
    print(0)
    exit()
for i in range(n):
    b*=a[i]
    if b>10**18:
        print(-1)
        exit()
print(b)
Buggy python submission (verdict: Runtime Error):
n,m,x=map(int,input().split())
a=[]
ans=-1
t=[0]*(m+1)
for i in range(n):
    a.append(list(map(int,input().split())))
for i in range(2 ** n):
    for j in range(n):
        if (i >> j) & 1:
            for lnd,l in enumerate(a[j]):
                t[lnd]+=l
    if ans==-1 or ans > t[0]:
        if min(t[1:m]) >= x:
            ans = t[0]
    t=[0]*(m+1)
print(ans)

Fixed submission:
n,m,x=map(int,input().split())
a=[]
ans=-1
t=[0]*(m+1)
for i in range(n):
    a.append(list(map(int,input().split())))
for i in range(2 ** n):
    for j in range(n):
        if (i >> j) & 1:
            for lnd,l in enumerate(a[j]):
                t[lnd]+=l
    if ans==-1 or ans > t[0]:
        if min(t[1:m+1]) >= x:
            ans = t[0]
    t=[0]*(m+1)
print(ans)
Buggy python submission (verdict: Runtime Error):
 print(n**3)

Fixed submission:
n=int(input())
print(n*n*n)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list(map(int,input().split()))
ans=0
for i in range(0,n-1):
    for j in range(i+2,n+1):
        ans+=sorted(set(p[i:j]))[-2]
print(ans)

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list(map(int,input().split()))
f=0
b=[]
t=0
c=[]
for i in range(n-1):
 for l in range(i+1,n):
  b=p[i:l+1]
  c.append(sorted(set(b))[-2])
print(sum(c))

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list(map(int,input().split()))
f=0
b=[]
t=0
c=[]
for i in range(n-1):
 for l in range(i+1,n):
  b=p[i:l+1]
  t=max(b)
  b.remove(t)
  for j in range(b.count(t)):
   b.remove(t)
  c.append(max(b))
print(sum(c))

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
p=list(map(int,input().split()))
f=0
b=[]
t=0
c=[]
for i in range(n-1):
 for l in range(i+1,n):
  b=p[i:l+1]
  t=max(b)
  b.remove(t)
  for j in range(b.count(t)):
   b.remove(t)
  c.append(max(b))
print(sum(c))

Fixed submission:
n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)