Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n = int(input())
A = [sorted(list(input())) for i in range(n)]
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if A[i] == A[j]:
            ans += 1
            
print(ans)

### FIXED CODE ###

N = int(input())
 
D = {}
for i in range(N):
    s = ''.join(sorted(input()))
    D.setdefault(s, 0)
    D[s] += 1
    
ans = 0
for v in D.values():
    if v > 1:
        for i in range(v):
            ans += i
    
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from math import sqrt

N,K=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

def calcdismax(x,y):
    TIME=[]
    for mx,my,c in M:
        TIME.append(c*sqrt((mx-x)**2+(my-y)**2))

    TIME.sort()

    #print(TIME)

    return TIME[K-1]

def div100(xmin,xmax,ymin,ymax):

    xh=(xmax-xmin)/200
    yh=(ymax-ymin)/200

    MIN=1<<30
    MINx=0
    MINy=0

    for i in range(201):
        xk=xmin+xh*i
        for j in range(201):
            yk=ymin+yh*j
            cd=calcdismax(xk,yk)

            #print(xk,yk,cd)

            if MIN>cd:
                MIN=cd
                MINx=xk
                MINy=yk

    #print(MINx,MINy,MIN)

    return MINx,MINy

now=1010
k=0
l=0
while now>10**(-10):
    k,l=div100(k-now,k+now,l-now,l+now)
    now/=2

print(calcdismax(k,l))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from math import sqrt

N,K=map(int,input().split())
M=[tuple(map(int,input().split())) for i in range(N)]

def cross_coor(x0,y0,c0,x1,y1,c1): # 二円の交点
    if (c1-c0)**2<=(x1-x0)**2+(y1-y0)**2<=(c0+c1)**2:
        x2,y2=x1-x0,y1-y0
        a=(x2**2+y2**2+c0**2-c1**2)/2

        xa=(a*x2+y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        ya=(a*y2-x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        xb=(a*x2-y2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+x0
        yb=(a*y2+x2*sqrt((x2**2+y2**2)*(c0**2)-a**2))/(x2**2+y2**2)+y0

        return [(xa,ya),(xb,yb)]
    else:
        return False

OK=1<<31
NG=0

while OK-NG>10**(-8):
    mid=(OK+NG)/2
    
    CANDI=[]
    for i in range(N):
        x0,y0,c0=M[i]
        CANDI.append((x0,y0))
        for j in range(i+1,N):
            x1,y1,c1=M[j]
            CR=cross_coor(x0,y0,mid/c0,x1,y1,mid/c1)
            if CR:
                CANDI.extend(CR)

    for z,w in CANDI:
        count=0
        for x,y,c in M:
            if (c**2)*((x-z)**2+(y-w)**2)<=(mid+10**(-8))**2:
                count+=1
            
        if count>=K:
            OK=mid
            break
    else:
        NG=mid

print((OK+NG)/2)
### BUGGY CODE ###

from bisect import bisect
N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
c = 0
for a in A:
 for b in B[bisect(B, a):] :
  c += N - bisect(C, b)
print(c)

### FIXED CODE ###

from bisect import bisect
N = int(input())
A = sorted(map(int, input().split()))
B = sorted(map(int, input().split()))
C = sorted(map(int, input().split()))
D = [0]*N
E = [0]*(N+1)
for i, b in enumerate(B) :
    D[i] = N - bisect(C, b)
for i, d in enumerate(D[::-1]) :
    E[N-i-1] = E[N-i] + d
c = 0
for a in A:
    c += E[bisect(B, a)]
print(c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def input_converter(key_string):
    key_string = key_string.replace('A', '1')
    key_string = key_string.replace('T', '2')
    key_string = key_string.replace('C', '3')
    key_string = key_string.replace('G', '4')
    return int(key_string)


class HashTable(object):
    def __init__(self, hash_size = 2 ** 20):
        self.hash_size = hash_size
        self.hash_array = [None] * self.hash_size

    def insert_value(self, data, key):
        collision_number = 0
        next_index = self.hash_function(key, collision_number)
        while self.hash_array[next_index] is not None:
            collision_number += 1
            next_index = self.hash_function(key, collision_number)
        # print self.hash_array[next_index]
        self.hash_array[next_index] = data

    def search_value(self, data, key):
        collision_number = 0
        next_index = self.hash_function(key, collision_number)
        while True:
            if (self.hash_array[next_index] is None) or (collision_number > self.hash_size):
                return False
            elif self.hash_array[next_index] == data:
                return True
            else:            
                collision_number +=1
                next_index = self.hash_function(key, collision_number)

    def hash_function(self, key, collision_number):
        def h1(key):
            return key % self.hash_size
    
        def h2(key):
            return key % (self.hash_size - 1)

        return (h1(key) + collision_number * h2(key)) % self.hash_size


def main():
    input_size = int(raw_input())
    hash_table = HashTable(2 ** 20)
    counter = 0
    while counter < input_size:
        command, key = raw_input().split(' ')
        if command == 'insert':
            hash_table.insert_value(key, input_converter(key))
        else:
            if hash_table.search_value(key, input_converter(key)):
                print 'yes'
            else:
                print 'no'
        counter += 1


if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

dictionary = {}
input_num = int(raw_input())
counter = 0
while counter < input_num:
    command, key = raw_input().split(' ')
    if command == 'insert':
        dictionary[key] = None
    else:
        if key in dictionary:
            print 'yes'
        else:
            print 'no'

    counter += 1
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(s: str):

    res = 0
    while True:
        cnt = s.count("ABC")
        if cnt == 0:
            break
        res += cnt
        s = s.replace("ABC","BCA")

    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def conv2num(c):
    if c == "A":
        return 1
    elif c == "D":
        return 2
    elif c == "B":
        return 3
    else:
        return 4

def solve(s: str):

    res = 0
    s = s.replace("BC","D")
    s = [ conv2num(c) for c in s ]

    acnt = 0
    for i,c in enumerate(s):
        if c == 1:
            acnt += 1
        elif c == 2:
            res += acnt
        else:
            acnt = 0


    print(res)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _dbg(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, K = inpl()
h = inpl()

INF = 10**10

dp = [INF] * N
dp[0] = 0

for j in range(1, N):
    for step in range(1, min(K, j)+1):
        dp[j] = min(dp[j], dp[j-step] + abs(h[j] - h[j-step]))
    _dbg(dp[1])

print(dp[N-1])

### FIXED CODE ###

import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _dbg(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, K = inpl()
h = inpl()

INF = 10**10

dp = [INF] * N
dp[0] = 0

for j in range(1, N):
    for step in range(1, min(K, j)+1):
        dp[j] = min(dp[j], dp[j-step] + abs(h[j] - h[j-step]))
    _dbg(dp[1])

print(dp[N-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, Q = [int(x) for x in input().split()]

edge = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

cost = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    cost[p - 1] += x

next = [0]
for i in next:
    for v in edge[i]:
        s_next = set(next)
        if v in s_next:
            continue
        next.append(v)
        cost[v] += cost[i]

print(" ".join(map(str, cost)))





### FIXED CODE ###

import sys
input = sys.stdin.readline

N, Q = [int(x) for x in input().split()]

edge = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = [int(x) for x in input().split()]
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

cost = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    cost[p - 1] += x

next = [0]
s_next = {0}
for i in next:
    for v in edge[i]:
        if v in s_next:
            continue
        s_next.add(v)
        next.append(v)
        cost[v] += cost[i]

print(" ".join(map(str, cost)))
### BUGGY CODE ###

#-*-coding:utf-8-*-

import sys

def main():
    k = int(input())
    mod=10**9+7
    if k % 2==0:
        print(-1)
        exit()

    sevens=7
    for i in range(1,10**6):
        if sevens%k==0:
            print(i)
            exit()
        else:
            sevens=(sevens*10+7)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-

import sys

def main():
    k = int(input())
    sevens=0
    for i in range(1,k+1):
        sevens=(sevens*10+7)%k
        if sevens==0:
            print(i)
            exit()
    print(-1)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
import queue
input = sys.stdin.readline
INF=float('inf')

def solve():
    n,m=map(int,input().split())
    l=[list(map(int,input().split())) for _ in range(m)]

    d=[INF]*n
    nbr=[[] for _ in range(n)]
    used=[False]*m

    for i in range(m):
        nbr[l[i][0]-1].append([l[i][0]-1,l[i][1]-1,l[i][2],i])
        nbr[l[i][1]-1].append([l[i][1]-1,l[i][0]-1,-l[i][2],i])
    #print(nbr)
    for i in range(n):
        if d[i]==INF:
            d[i]=0
            q=queue.Queue()
            for x in nbr[i]:
                q.put(x)
            while not q.empty():
                eg=q.get()
                used[eg[3]]=True
                if d[eg[1]]==d[eg[0]]+eg[2]:
                    pass
                elif d[eg[1]]==INF:
                    d[eg[1]]=d[eg[0]]+eg[2]
                else:
                    print('No')
                    exit()
                for x in nbr[eg[1]]:
                    if not used[x[3]]:
                        q.put(x)
    #print(d)
    print('Yes')
solve()

### FIXED CODE ###

def solve():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**6)
    INF=float('inf')
    n,m=map(int,input().split())
    l=[list(map(int,input().split())) for _ in range(m)]
    d=[INF]*n
    nbr=[[] for _ in range(n)]
    used=[False]*m
    for x in l:
        x[0]-=1
        x[1]-=1
    #print(l)
    for i in range(m):
        nbr[l[i][0]].append(i)
        nbr[l[i][1]].append(i)
    #print(nbr)
    def sol(i):
        for x in nbr[i]:
            if used[x]:continue
            used[x]=True
            i1=l[x][0]^l[x][1]^i
            dd=d[i]+l[x][2]*(2*(l[x][0]==i)-1)
            if d[i1]!=dd and d[i1]!=INF:
                print('No')
                exit()
            elif d[i1]==INF:
                d[i1]=dd
                sol(i1)
    for i in range(n):
        if d[i]==INF:
            d[i]=0
            sol(i)
    #print(d)
    print('Yes')
solve()
### BUGGY CODE ###

from heapq import heappush, heappop
N=int(input())
road=[[float("inf") for _ in range(N)]for _ in range(N)]
pq=[]
ans=0
for i in range(N):
    road[i][i]=0
    tmp=list(map(int,input().split()))
    for j in range(i+1,N):
        heappush(pq,(tmp[j],i,j))

while pq:
    v=heappop(pq)
    d,i,j=v[0],v[1],v[2]
    tmp=road[i][j]
    for k in range(N):
        tmp=min(tmp,road[i][k]+road[k][j])
    if tmp>d:
        road[i][j]=d
        road[j][i]=d
        ans+=d
    elif tmp==d:
        road[i][j]=d
        road[j][i]=d
    else:
        print(-1)
        exit()
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop
def main():
    N=int(input())
    road=[[float("inf") for _ in range(N)]for _ in range(N)]
    pq=[]
    ans=0
    for i in range(N):
        road[i][i]=0
        tmp=list(map(int,input().split()))
        for j in range(i+1,N):
            heappush(pq,(tmp[j],i,j))

    while pq:
        v=heappop(pq)
        d,i,j=v[0],v[1],v[2]
        tmp=road[i][j]
        for k in range(N):
            tmp=min(tmp,road[i][k]+road[k][j])
            if tmp==d:
                break
        if tmp>d:
            road[i][j]=d
            road[j][i]=d
            ans+=d
        elif tmp==d:
            road[i][j]=d
            road[j][i]=d
        else:
            print(-1)
            exit()
    print(ans)
main()
### BUGGY CODE ###

s = input()
n = len(s)
ans = 0

for i in range(n):
  k = len(s[i:])+1
  for j in range(i+1,n+1):
    if int(s[i:j])%2019 == 0:
      ans += 1

print(ans)

### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))
### BUGGY CODE ###

a, b, k = map(int, input().split())
li = []
for i in range(a, b+1):
    if i < a+k or i > b-(k):
        li.append(i)
s = set(li)
d = sorted(s)
for x in d:
    print(x)

### FIXED CODE ###

a, b, k = map(int, input().split())
li = []
for i in range(a, a+k):
    if a <= i <= b:
        li.append(i)
for j in range(b-k+1, b+1):
    if a <= i <= b:
        li.append(j)
s = set(li)
d = sorted(s)
for x in d:
    print(x)
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N)]
for row in sys.stdin.readlines():
    x,y = map(int,row.split())
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

ldp = [None] * N
rdp = [None] * N

def dfs_1(v=0,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    graph[v].discard(parent)
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(reversed(vals),1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

def dfs_2(v=0,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    dp[v] = x * ldp[v][-1] % MOD
    for w,p,q in zip(graph[v],ldp[v][:-1],rdp[v][1:]):
        dfs_2(w,x*p*q%MOD+1)

dp = [None] * N
dfs_2()

print('\n'.join(map(str,dp)))

### FIXED CODE ###

import itertools
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N)]
for row in sys.stdin.readlines():
    x,y = map(int,row.split())
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

ldp = [None] * N
rdp = [None] * N

def dfs_1(v=0,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    graph[v].discard(parent)
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(reversed(vals),1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

dp = [None] * N
q = [(0,1)]
while q:
    v,x = q.pop()
    dp[v] = x*ldp[v][-1]%MOD
    for w,L,R in zip(graph[v],ldp[v][:-1],rdp[v][1:]):
        q.append((w,x*L*R%MOD+1))

print('\n'.join(map(str,dp)))
### BUGGY CODE ###

def main():
  from array import array
  from collections import defaultdict
  from heapq import heappush,heappop,heapify
  A=array
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:
      l.append(y)
      d[y]=inf
    edge[a].append(A('L',[1,x]))
    edge[b].append(A('L',[1,y]))
    edge[x].extend([A('L',[0,a]),A('L',[0,y])])
    edge[y].extend([A('L',[0,b]),A('L',[0,x])])
    used[a]=used[b]=used[x]=used[y]=True
  used[1]=False
  edgelist=edge[1]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,A('L',[e[0]+m[0],e[1]]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print(-1)
    exit()
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(int)
start={i for i in range(N)}
for i in range(N+M-1):
    a,b=map(int,input().split())
    start-={b-1}
    OUT[a-1]|={b-1}
    IN[b-1]+=1
P=[0]*N
while len(start)>0:
    now=start.pop()
    for nex in OUT[now]:
        IN[nex]-=1
        if IN[nex]==0:
            start|={nex}
            P[nex]=now+1
for p in P:
    print(p)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
from collections import defaultdict
OUT=defaultdict(set)
IN=defaultdict(int)
for i in range(N+M-1):
    a,b=map(int,input().split())
    OUT[a-1]|={b-1}
    IN[b-1]+=1
P=[0]*N
start={i for i in range(N) if IN[i]==0}
while len(start)>0:
    now=start.pop()
    for nex in OUT[now]:
        IN[nex]-=1
        if IN[nex]==0:
            start|={nex}
            P[nex]=now+1
[print(p) for p in P]
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
  N,M=map(int,input().split())
  R=[i for i in range(N)]
  L=list(map(int,input().split()))
  for i in range(M):
    t,u=map(int,input().split())
    if L[t-1]<=L[u-1] and t-1 in R:
      R.remove(t-1)
    if L[t-1]>=L[u-1] and u-1 in R:
      R.remove(u-1)
  print(len(R))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())
def NIJIGEN(H): return [list(input()) for i in range(H)]
N,M=MAP()
H=LIST()
L=[[0] for i in range(N)]
for i in range(M):
  a,b=MAP()
  a-=1
  b-=1
  L[a].append(H[b])
  L[b].append(H[a])
ans=0
for i in range(N):
  if max(L[i])<H[i]:
    ans+=1
print(ans)
### BUGGY CODE ###

from collections import Counter

N, *A = map(int, open(0).read().split())

ctr = Counter(A)
memo = set()
ans = 0

for a in sorted(set(A)):
    if a == 1:
        if ctr[a] == 1:
            ans = 1
        break

    for i in range(1, int(a ** 0.5) + 1):
        if a % i == 0:
            if (i in memo) or (a // i in memo):
                break
    else:
        if ctr[a] == 1:
            ans += 1

    memo.add(a)
        
print(ans)


### FIXED CODE ###

from collections import Counter

N, *A = map(int, open(0).read().split())

m = max(A) + 1
ok = [True] * m
ctr = Counter(A)
ans = 0
for a in sorted(A):
    if ok[a] and ctr[a] == 1:
        ans += 1
        
    for j in range(2 * a, m, a):
        ok[j] = False
            
print(ans)
### BUGGY CODE ###

from functools import reduce
n = int(input())
a = list(map(int, input().split()))

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

def gcd_list(ns):
    return reduce(gcd, ns)

# l[i]:a[i]を含まない前方要素の最大公約数
l = [0 for _ in range(n)]
l[0] = 0
for i in range(1, n):
    l[i] = gcd_list(a[0:i])
# print(l)

# r[i]:a[i]を含まない後方要素の最大公約数
r = [0 for _ in range(n)]
r[-1] = 0
for i in range(0, n-1):
    r[i] = gcd_list(a[i+1:n])
# print(r)

ans = 0
for i in range(n):
    ans = max(ans, gcd(l[i],r[i]))

print(ans)

### FIXED CODE ###

from functools import reduce

# 2数の最大公約数
def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

# リストの最大公約数
def gcd_list(nums):
    return reduce(gcd, nums)

# 入力
n = int(input())
a = list(map(int, input().split()))

#a[i]より前方要素の最大公約数を保持
l = [0 for _ in range(n)]
l[0] = 0
for i in range(1, n):
    l[i] = gcd(l[i-1], a[i-1])
# print(l)

#a[i]より後方要素の最大公約数を保持
r = [0 for _ in range(n)]
r[n-1] = 0
for i in reversed(range(n-1)):
    r[i] = gcd(r[i+1], a[i+1])
# print(r)

# a[i]を除いた最大公約数を計算
ans = 0
for i in range(n):
    ans = max(ans, gcd(l[i],r[i]))

# 出力
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
capacity = [1 for k in range(N+1)]
cut = 0
for k in range(N+1):
    #print(capacity)
    if A[k] >= capacity[k] and k!= N:
        print(-1)
        break
    if A[k] > capacity[k] and k == N:
        print(-1)
        break
    if k < N:
        capacity[k+1] = 2*(capacity[k] - A[k])
    if k == N:
        ans = [0 for k in range(N+1)]
        ans[0] =1
        for j in range(N+1):
            for m in range(j+1):
                ans[m] = min(capacity[m], ans[m] + A[j])
        print(sum(ans))





### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
capacity = [1 for k in range(N+1)]
cut = 0
for k in range(N+1):
    #print(capacity)
    if A[k] >= capacity[k] and k!= N:
        print(-1)
        break
    if A[k] > capacity[k] and k == N:
        print(-1)
        break
    if k < N:
        capacity[k+1] = 2*(capacity[k] - A[k])
    if k == N:
        ans = [0 for k in range(N+1)]
        ans[0] =1
        sumA = 0
        for m in range(1, N+2):
            sumA += A[-m]
            ans[-m] = min(capacity[-m], sumA)
        print(sum(ans))