Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math
n = int(input())

def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

sq = math.sqrt(n)
if sq.is_integer():
    ansInt = sq

if is_prime(n):
    ansInt = n
else:
    ansInt = prime_decomposition(n)
print(len(str(int(max(ansInt)))))

Fixed submission:
n = int(input())
ans = len(str(n))
a = 0
while a**2 <= n:
    a += 1
    if n % a != 0:
        continue
    b = n // a
    cur = max(len(str(a)), len(str(b)))
    if ans > cur:
        ans = cur
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
x = int(input())
for i in range(1, x+1):
    if sum([j for j in range(1, i+1)]) >= x:
        print(i)
        break

Fixed submission:
x = int(input())
for i in range(1, x+1):
    if i * (i+1) / 2 >= x:
        print(i)
        break
Buggy python submission (verdict: Time Limit Exceeded):
k, s = map(int, input().split())
count = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i + j + l == s:
                count += 1
print(count)

Fixed submission:
k, s = map(int, input().split())
count = 0
for i in range(k+1):
    for j in range(k+1):
        if 0 <= s - (i + j) <= k:
            count += 1
print(count)
Buggy python submission (verdict: Runtime Error):
n, l = map(int, input().split())
sList = []
for i in range(n):
    sList.append()
sList.sort()
print(''.join(sList))

Fixed submission:
n, l = map(int, input().split())
sList = []
for i in range(n):
    sList.append(input())
sList.sort()
print(''.join(sList))
Buggy python submission (verdict: Runtime Error):
x = input()
if(x >= 30):
  print('Yes')
  else:
        print('No')

Fixed submission:
x = int(input())
if x >= 30:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Runtime Error):
R =int(input())
print("2 * 3.1415926535 * R)


Fixed submission:
r = float(input())
print(2 * r * 3.14159265)
Buggy python submission (verdict: Runtime Error):
n, k, x, y = map(int, input().split())

print(int(k * x + y * (n - k)))


Fixed submission:
# x, y = [int(input()) for i in range(2)]
n, k, x, y = [int(input()) for i in range(4)]

if n > k:
    print(int(k * x + y * (n - k)))
else:
    print(int(n * x))
Buggy python submission (verdict: Runtime Error):
# list に入力を格納
list = list(int, input().split())
# 小さい順に並び替え
list.sort()

if list[0] == 5 and list[1] == 5 and list[2] == 7:
    print('Yes')
else:
    print('No')


Fixed submission:
# list に入力を格納
list = list(map(int, input().split()))
# 小さい順に並び替え
list.sort()

if list[0] == 5 and list[1] == 5 and list[2] == 7:
    print('YES')
else:
    print('NO')

Buggy python submission (verdict: Runtime Error):
# list に入力を格納
list = list(map(int, input().split()))
# 小さい順に並び替え
list.sort()

if list[0] == 5 and list[1] == 5 and list[7] == 7:
    print('Yes')
else:
    print('No')


Fixed submission:
# list に入力を格納
list = list(map(int, input().split()))
# 小さい順に並び替え
list.sort()

if list[0] == 5 and list[1] == 5 and list[2] == 7:
    print('YES')
else:
    print('NO')

Buggy python submission (verdict: Runtime Error):

list = list(int, input().split())

list.sort()

if list[0] == 5 and list[1] == 5 and list[7] == 7:
    print('Yes')
else:
    print('No')


Fixed submission:
# list に入力を格納
list = list(map(int, input().split()))
# 小さい順に並び替え
list.sort()

if list[0] == 5 and list[1] == 5 and list[2] == 7:
    print('YES')
else:
    print('NO')

Buggy python submission (verdict: Runtime Error):
# list に入力を格納
list = list(int, input().split())
# 小さい順に並び替え
list.sort()

if list[0] == 5 and list[1] == 5 and list[7] == 7:
    print('Yes')
else:
    print('No')


Fixed submission:
# list に入力を格納
list = list(map(int, input().split()))
# 小さい順に並び替え
list.sort()

if list[0] == 5 and list[1] == 5 and list[2] == 7:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Runtime Error):
s, t = map(str, input().split())
a, b = map(int, input().split())
u = input()
if u == s:
  a -= 1
 else:
  b -= 1
 print(a, b)

Fixed submission:
s, t = map(str, input().split())
a, b = map(int, input().split())
u = input()
if u == s:
  a -= 1
else:
  b -= 1
print(a, b)
Buggy python submission (verdict: Runtime Error):
if int(input()) > 30 print('Yes') else print('No')

Fixed submission:
print('Yes') if (int(input())) >= 30 else print('No')

Buggy python submission (verdict: Runtime Error):
input()
s = input()

def find_cost(s):
    counter, i, j = 0, 0, len(s)-1
    while i < j:
        while i < len(s) and s[i] != 'W':
                i += 1
        while j >= 0 and s[j] != 'R':
                j -= 1
        if i < j:
            s[i], s[j] = s[j], s[i]
            counter += 1
        i += 1
        j -= 1
    for i in range(0, len(s) - 2):
        if s[i] == 'W' and s[i + 1] == 'R':
            counter += 1
    print(counter)
s = list(s)
find_cost(s)

Fixed submission:
print('Yes') if (int(input())) >= 30 else print('No')
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N,M,K = inputMap()
	A = inputList()
	B = inputList()

	sumA = sum(A)
	sumB = sum(B)
	if sumA + sumB <= K:
		print(N+M)
		sys.exit()

		A.append(inf)
		B.append(inf)

	ans = 0
	times = 0

	while True:
		if times > K:
			break

		if A[0] < B[0]:
			times += A[0]
			A = A[1:]
		else:
			times += B[0]
			B = B[1:]
		#print(times)
		ans += 1

	print(ans-1)



#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Fixed submission:
N, M, K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
a, b=[0], [0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])
ans, j=0, M
for i in range(N+1):
    if a[i]>K:
        break
    while b[j]>K-a[i]:
        j-=1
    ans=max(ans, i+j)
print(ans)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
import sympy
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()

	ans = 0
	for i in range(N+1):
		tmp = sympy.divisor_count(i)
		#print(tmp)
		tmp = i * tmp
		ans += tmp

	print(ans)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	Nnum = [0 for i in range(N+1)]

	for i in range(1,N+1):
		for j in range(i,N+1,i):
			Nnum[j] += 1

	ans = 0
	for i,val in enumerate(Nnum):
		ans += i * val

	print(ans)



#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()

	print(alpha2num(N).upper())


def alpha2num(alpha):
    num=0
    for index, item in enumerate(list(alpha)):
        num += pow(26,len(alpha)-index-1)*(ord(item)-ord('A')+1)
    return num

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()

	print(num2alpha(N).lower())


def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	LR = []
	min_i = -1
	max_i = -1
	for i in range(M):
		L, R = map(int, input().split(" "))
		LR.append((L, R))
		if i == 0:
			min_i = L
			max_i = R
		else:
			if L < min_i:
				min_i = L
			if max_i < R:
				max_i = R

	ans = 0
	for i in range(min_i, max_i+1):
		flg = True
		for j in LR:
			L, R = j

			if i <= R and i >= L:
				flg = True
			else:
				flg = False
				break
		if flg == True:
			#print("sss")
			ans += 1

	print(ans)


if __name__ == "__main__":
	main()

Fixed submission:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	LR = []
	min_i = -1
	max_i = -1
	min_a = -1
	max_a = -1
	for i in range(M):
		L, R = map(int, input().split(" "))
		LR.append((L, R))
		if i == 0:
			min_i = L
			max_i = R
			min_a = L
			max_a = R
		else:
			if L > min_i:
				min_i = L
			if max_i > R:
				max_i = R

	ans = 0
	for i in range(min_i, max_i+1):
		ans += 1

	print(ans)


if __name__ == "__main__":
	main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	R, G, B, N = map(int, input().split(" "))
	
	ans = 0
	for i in range(N+1):
		r = i * R
		for j in range(N+1):
			g = j * G
			if N - r - g < 0:
				continue
			if (N - r - g) % B != 0:
				continue
			k = (N - r - g) // B
			#print("{} {} {}".format(i, j, k))
			ans += 1
			

	print(ans)

	
	
if __name__ == "__main__":
	main()

Fixed submission:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	R, G, B, N = map(int, input().split(" "))
	
	ans = 0
	for i in range(N+1):
		r = i * R
		for j in range(N+1):
			g = j * G
			if N - r - g < 0:
				continue
			if (N - r - g) % B != 0:
				continue
			#k = (N - r - g) // B
			#print("{} {} {}".format(i, j, k))
			ans += 1
			

	print(ans)

	
	
if __name__ == "__main__":
	main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
input = sys.stdin.readline

# bisect_left(lists, 3)
# bisect_right(lists, 3)

def main():
	X, Y, Z, K = map(int, input().split(" "))
	As = []
	Bs = []
	Cs = []
	As = input().split()
	As = [int(s) for s in As]
	Bs = input().split()
	Bs = [int(s) for s in Bs]
	Cs = input().split()
	Cs = [int(s) for s in Cs]

	As.sort(reverse=True)
	Bs.sort(reverse=True)
	Cs.sort(reverse=True)

	As = As[:K]
	Bs = Bs[:K]
	Cs = Cs[:K]

	ans = []
	for i, val in enumerate(As):
		for j, vol in enumerate(Bs):
			for k, ogi in enumerate(Cs):
				ans.append(val+vol+ogi)

	ans.sort(reverse=True)
	for i in range(K):
		print(ans[i])
	
if __name__ == "__main__":
	main()
	

Fixed submission:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
input = sys.stdin.readline

# bisect_left(lists, 3)
# bisect_right(lists, 3)

def main():
	X, Y, Z, K = map(int, input().split(" "))
	As = []
	Bs = []
	Cs = []
	As = input().split()
	As = [int(s) for s in As]
	Bs = input().split()
	Bs = [int(s) for s in Bs]
	Cs = input().split()
	Cs = [int(s) for s in Cs]

	As.sort(reverse=True)
	Bs.sort(reverse=True)
	Cs.sort(reverse=True)

	ans1 = []
	for i, val in enumerate(As):
		for j, vol in enumerate(Bs):
			ans1.append(val+vol)

	ans1.sort(reverse=True)
	ans1 = ans1[:3000]

	ans2 = []
	for i, val in enumerate(ans1):
		for j, vol in enumerate(Cs):
			ans2.append(val+vol)

	ans2.sort(reverse=True)
	for i in range(K):
		print(ans2[i])
	
if __name__ == "__main__":
	main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
import collections
import re
import copy

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	pattern = r"AC"
	
	Qs = []
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		Qs.append((l, r))
	
	ans = []
	for i, val in enumerate(Qs):
		l, r = val
		tmp = S[l-1:r]
		matchedList = re.findall(pattern, "".join(tmp))
		
		ans.append(len(matchedList))
	
	
	for i in ans:
		print(i)
	
if __name__ == "__main__":
	main()
	

Fixed submission:
# -*- coding: utf-8 -*-
import sys

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	
	Qs = []
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		Qs.append((l, r))
	
	ptn = []
	hit = 0
	flg = False
	for i, val in enumerate(S):
		if val == "A":
			ptn.append(hit)
			if i+1 < len(S) and S[i+1] == "C":
				hit += 1
				ptn.append(hit)
				flg = True
		else:
			if flg == False:
				ptn.append(hit)
			else:
				flg = False
		
	ans = []
	for i, val in enumerate(Qs):
		l, r = val
		if l == r:
			ans.append(0)
			break
			
		tmp = ptn[r-1] - ptn[l-1]
		ans.append(tmp)
	
	
	for i in ans:
		print(i)
	
if __name__ == "__main__":
	main()

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
import collections

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	
	Qs = []
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		Qs.append((l, r))
	
	ans = []
	for i, val in enumerate(Qs):
		l, r = val
		tmp = S[l-1:r]
		ans_t = 0
		
		for j, val in enumerate(tmp):
			if val == "A":
				if j+1 < len(tmp) and tmp[j+1] == "C":
					ans_t += 1
		ans.append(ans_t)
	
	
	for i in ans:
		print(i)
	
if __name__ == "__main__":
	main()
	

Fixed submission:
# -*- coding: utf-8 -*-
import sys

def main():
	N, Q = map(int, input().split(" "))
	S = input()
	S = list(S)
	
	Qs = []
	for _ in range(Q):
		l, r = map(int, input().split(" "))
		Qs.append((l, r))
	
	ptn = []
	hit = 0
	flg = False
	for i, val in enumerate(S):
		if val == "A":
			ptn.append(hit)
			if i+1 < len(S) and S[i+1] == "C":
				hit += 1
				ptn.append(hit)
				flg = True
		else:
			if flg == False:
				ptn.append(hit)
			else:
				flg = False
		
	ans = []
	for i, val in enumerate(Qs):
		l, r = val
		if l == r:
			ans.append(0)
			break
			
		tmp = ptn[r-1] - ptn[l-1]
		ans.append(tmp)
	
	
	for i in ans:
		print(i)
	
if __name__ == "__main__":
	main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys

def main():
	A, B = map(int, input().split(" "))
	
	ans = A
	for i in range(A+1, B+1):
		ans = ans ^ i
		
	print(ans)
	
if __name__ == "__main__":
	main()
	

Fixed submission:
# -*- coding: utf-8 -*-
import sys

def main():
	A, B = map(int, input().split(" "))
	
	B0 = 0
	if B % 2 == 1:
		tmp = (B + 1) // 2
		if tmp % 2 == 1: B0 = 1
		else: B0 = 0
	else:
		tmp = B // 2
		if tmp % 2 == 1: B0 = 1
		else: B0 = 0
		B0 = B0 ^ B
		
	A0 = 0
	if (A-1) % 2 == 1:
		tmp = A // 2
		if tmp % 2 == 1: A0 = 1
		else: A0 = 0
	else:
		tmp = (A-1) // 2
		if tmp % 2 == 1: A0 = 1
		else: A0 = 0
		A0 = A0 ^ (A-1)
		
	print(B0 ^ A0)
		
if __name__ == "__main__":
	main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys

def main():
	N, M = map(int, input().split(" "))
	
	bridge = []
	for _ in range(M):
		a, b = map(int, input().split(" "))
		bridge.append((a, b))
		
	bridge.reverse()
	uf = UnionFind(N)
	ans = []
	fuben = 0
	for i in range(N):
		for j in range(N):
			if i < j:
				if False == uf.is_same(i, j):
					fuben += 1
	ans.append(fuben)
	
	for i, val in enumerate(bridge):
		a, b = val
		a, b = a-1, b-1
		uf.union(a, b)
		fuben = 0
		for i in range(N):
			for j in range(N):
				if i < j:
					if False == uf.is_same(i, j):
						fuben += 1
		ans.append(fuben)
		
	ans.pop()
	ans.reverse()
	for val in ans:
		print(val)
	

class UnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		
	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]
		
	# x と y のグループを結合
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				x, y = y, x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self.par[y] = x
	
	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)
		

if __name__ == "__main__":
	main()
	

Fixed submission:
# -*- coding: utf-8 -*-
import sys
import collections

def main():
	N, M = map(int, input().split(" "))
	
	bridge = []
	for _ in range(M):
		a, b = map(int, input().split(" "))
		bridge.append((a, b))
		
	bridge.reverse()
	uf = UnionFind(N)
	ans = []
	fuben = 0
	ans.append(N * (N-1) // 2)
	
	for i, val in enumerate(bridge):
		a, b = val
		a, b = a-1, b-1
		if False == uf.is_same(a, b):
			child_a = uf.getCoun(a)
			child_b = uf.getCoun(b)
			ans.append(ans[i] - (child_a * child_b))
		else:
			ans.append(ans[i])
		uf.union(a, b)
		
	ans.pop()
	ans.reverse()
	for val in ans:
		print(val)
	

class UnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		self.size = [1 for _ in range(n)]
		
	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]
		
	# x と y のグループを結合
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			x_size = self.size[x]
			y_size = self.size[y]
			sum = x_size + y_size
			self.size[x] = sum
			self.size[y] = sum
			if self.rank[x] < self.rank[y]:
				x, y = y, x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self.par[y] = x
	
	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)
		
	def getCoun(self, a):
		x = self.find(a)
		return self.size[x]

if __name__ == "__main__":
	main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left

def main():
	N = int(input())
	V = input().split(" ")
	
	K = []
	G = []
	for i, val in enumerate(V):
		if i % 2 == 0:
			G.append(val)
		else:
			K.append(val)
	
	k = collections.Counter(K)
	k = sorted(k.items(), key=lambda x:x[1], reverse=True)
	g = collections.Counter(G)
	g = sorted(g.items(), key=lambda x:x[1], reverse=True)
	
	aaa, bbb = k[0]
	ccc, ddd = g[0]
	
	if aaa == ccc:
		if bbb > ddd and len(g) > 0:
			tmp1, tmp2 = g[1]
			g[0] = (tmp1, tmp2)
			g[1] = (ccc, ddd)
		elif bbb <= ddd and len(k) > 0:
			tmp1, tmp2 = k[1]
			k[0] = (tmp1, tmp2)
			k[1] = (aaa, bbb)
	
	#print(k)
	#print(g)
		
	ans = 0
	sono1 = 0
	sono2 = 0
	for a, b in enumerate(k):
		i, j = b
		if a == 0:
			sono1 = i
			continue
		ans += j
	
	for a, b in enumerate(g):
		i, j = b
		if a == 0:
			sono2 = i
			continue
		ans += j
		
	if ans > 0:
		print(ans)
	elif sono1 != sono2:
		print(ans)
	else:
		print(len(K))
		
		
	
if __name__ == "__main__":
	main()


Fixed submission:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left

def main():
	N = int(input())
	V = input().split(" ")
	
	K = []
	G = []
	for i, val in enumerate(V):
		if i % 2 == 0:
			G.append(val)
		else:
			K.append(val)
	
	k = collections.Counter(K)
	k = sorted(k.items(), key=lambda x:x[1], reverse=True)
	g = collections.Counter(G)
	g = sorted(g.items(), key=lambda x:x[1], reverse=True)
	
	aaa, bbb = k[0]
	ccc, ddd = g[0]
	eee = -1
	fff = -1
	ggg = -1
	hhh = -1
	if len(k) > 1:
		eee, fff = k[1]
	if len(g) > 1:
		ggg, hhh = g[1]
	
	if aaa == ccc:
		if bbb > ddd and ggg != -1:
			g[0] = (ggg, hhh)
			g[1] = (ccc, ddd)
		elif bbb < ddd and eee != -1:
			k[0] = (eee, fff)
			k[1] = (aaa, bbb)
		elif ggg != -1:
			if fff >= hhh:
				k[0] = (eee, fff)
				k[1] = (aaa, bbb)
			else:
				g[0] = (ggg, hhh)
				g[1] = (ccc, ddd)
	
	#print(k)
	#print(g)
		
	ans = 0
	sono1 = 0
	sono2 = 0
	for a, b in enumerate(k):
		i, j = b
		if a == 0:
			sono1 = i
			continue
		ans += j
	
	for a, b in enumerate(g):
		i, j = b
		if a == 0:
			sono2 = i
			continue
		ans += j
		
	if ans > 0:
		print(ans)
	elif sono1 != sono2:
		print(ans)
	else:
		print(len(K))
		
		
	
if __name__ == "__main__":
	main()