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

import bisect

n=int(input())
l=sorted(list(map(int,input().split())))

ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=bisect.bisect_left(l[j+1:], l[i]+l[j])

print(ans)


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
 
ans = 0
for i in range(N):  # １番短い棒
    for j in range(i + 1, N):  # 真ん中の長さの棒
        ans += bisect_left(L, L[i] + L[j]) - (j + 1)
 
print(ans)
### BUGGY CODE ###

import copy
n=int(input())
list=[int(input()) for i in range(n)]
max = 0
for i in range(n):
    temp_list = copy.copy(list)
    temp_list.pop(i)
    temp_list.sort(reverse=True)
    print(temp_list[0])

### FIXED CODE ###

import copy
n=int(input())
list=[int(input()) for i in range(n)]
temp_list = copy.copy(list)
temp_list.sort(reverse=True)

max = 0
for c in list:
    if(c == temp_list[0]):
        print(temp_list[1])
    else:
        print(temp_list[0])
### BUGGY CODE ###

import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(1100000)
N = int(input())
side = [[[]for _ in range(N)]for _ in range(N)] 
node = [[1]*N for i in range(N)]
for i in range(N):
    A = list(map(int,input().split()))
    for j in range(N-2):
        a,b = min(i,A[j]-1),max(i,A[j]-1)
        c,d = min(i,A[j+1]-1),max(i,A[j+1]-1)
        side[a][b].append([c,d])
        node[c][d] = 0
def DFS(x,y,l):
    if l > N**2:
        print(-1)
        exit()
    ret = l
    for i,j in side[x][y]:
        ret = max(ret, DFS(i,j,l+1))
    return ret


ans = 0
for i in range(N):
    for j in range(i+1,N):
        if node[i][j]:
            ans = max(DFS(i,j,1),ans)
if ans:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

N = int(input())
A = list(list(map(int,input().split()))for _ in range(N))

c = [0]*(N)
p = []
for i in range(N):
    j = A[i][c[i]]-1
    if i == A[j][c[j]]-1 and i < j:
        p.append((i,j))
ans = 0
while p:
    q = []
    for i,j in p:
        c[i] += 1
        c[j] += 1
        if c[i] < N-1:
            k = A[i][c[i]]-1
            if A[k][c[k]]-1 == i:
                q.append((i,k))
        if c[j] < N-1:
            k = A[j][c[j]]-1
            if A[k][c[k]]-1 == j:
                q.append((j,k))
    ans += 1
    p = q[:]

if min(c) != N-1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

from math import ceil, log2


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.aggfunc = aggfunc
        self.depth = ceil(log2(length))
        self.data = [init_value] * (2 ** (1 + self.depth) - 1)
        self.origin = 2 ** self.depth - 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])


n, q = map(int, input().split())
stx = [map(int, input().split()) for _ in range(n)]
d = [int(input()) for _ in range(q)]
xs = set()
events = []

for s, t, x in stx:
    events.append((s - x, 1, x))
    events.append((t - x, -1, x))
    xs.add(x)
events.sort()

xs = list(xs)
xs.sort()


zaatsu = dict(zip(xs, range(len(xs))))

ub = 10 ** 9 + 1
koujichu = SegmentTree(len(zaatsu), ub, min)

i = 0
for di in d:
    while i < len(events) and events[i][0] <= di:
        if events[i][1] == 1:
            koujichu.update(zaatsu[events[i][2]], events[i][2])
        else:
            koujichu.update(zaatsu[events[i][2]], ub)
        i += 1
    if koujichu.data[0] != ub:
        print(koujichu.data[0])
    else:
        print(-1)


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

stx.sort(key=lambda x: x[2])

ans = [-1] * q
jump = [-1] * q
for s, t, x in stx:
    d_start = bisect_left(d, s - x)
    d_stop = bisect_left(d, t - x, lo=d_start)
    while d_start < d_stop:
        if jump[d_start] == -1:
            ans[d_start] = x
            jump[d_start] = d_stop
            d_start += 1
        else:
            d_start = jump[d_start]

for an in ans:
    print(an)
### BUGGY CODE ###

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools



sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N = int(input())
A =  [int(i) for i in input().split()]
ans = 1

for i in range(N):
    ans *= A[i]

if(10**18<ans):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools



sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N = int(input())
A =  [int(i) for i in input().split()]
ans = 1
flag = 0

for i in range(N):
    ans *= A[i]
    if(10**18<ans):
        flag = 1
        break

if(0 in A):
    print(0)
elif(flag == 1):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict
input=sys.stdin.readline
d=defaultdict(int)
R,C,k=map(int,input().split())
for i in range(k):
  r,c,v=map(int,input().split())
  d[(r-1)*C+c-1]=v
dp=[[[0,0,0,0] for j in range(C+1)] for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    V=d[(i-1)*C+(j-1)]
    dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i-1][j][3],dp[i][j-1][0])
    dp[i][j][1]=max(dp[i][j][0]+V,dp[i][j-1][1])
    dp[i][j][2]=max(dp[i][j-1][1]+V,dp[i][j-1][2])
    dp[i][j][3]=max(dp[i][j-1][2]+V,dp[i][j-1][3])
print(max(dp[-1][-1]))

### FIXED CODE ###

import sys
input=sys.stdin.readline
R,C,k=map(int,input().split())
A=[[0]*C for i in range(R)]
for i in range(k):
  r,c,v=map(int,input().split())
  A[r-1][c-1]=v
dp0=[[0]*(C+1) for i in range(R+1)]
dp1=[[0]*(C+1) for i in range(R+1)]
dp2=[[0]*(C+1) for i in range(R+1)]
dp3=[[0]*(C+1) for i in range(R+1)]
for i in range(1,R+1):
  for j in range(1,C+1):
    V=A[i-1][j-1]
    dp0[i][j]=max(dp0[i-1][j],dp1[i-1][j],dp2[i-1][j],dp3[i-1][j],dp0[i][j-1])
    dp1[i][j]=max(dp0[i][j]+V,dp1[i][j-1])
    dp2[i][j]=max(dp1[i][j-1]+V,dp2[i][j-1])
    dp3[i][j]=max(dp2[i][j-1]+V,dp3[i][j-1])
print(max(dp0[-1][-1],dp1[-1][-1],dp2[-1][-1],dp3[-1][-1]))
### BUGGY CODE ###

n, k, q = map(int, input().split())
points = [k] * n

mi = lambda x: x - 1

for _ in range(q):
    win = int(input())
    #points = [p-1 for p in points]
    points = list(map(mi, points))
    points[win-1] += 1

for i in points:
    if i >= 1:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

n, k, q = map(int, input().split())
points = [k] * n


for _ in range(q):
    win = int(input())
    points[win-1] += 1

points = [p-q for p in points]
for i in points:
    if i >= 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,m=map(int,input().split())
p=list(map(int,input().split()))
r=[i for i in range(n)]
sp=[{p[i]-1} for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
    sp[ry]=sp[rx]|sp[ry]
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def get(x):
  return sp[root(x)]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if (i in get(i)) or i+1==p[i]:
    ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
p=list(map(int,input().split()))
r=[i for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if root(i)==root(p[i]-1) or i+1==p[i]:
    ans+=1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

p = int(1e9+7)
res = 0

for i in range(60):
    zc = 0
    oc = 0
    for j in range(len(A)):
        if A[j] % 2 == 0:
            zc += 1
        else:
            oc += 1
        A[j] = A[j] >> 1

    res += zc*oc*2**i
    res %= p

print(res)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

p = int(1e9+7)
res = 0

for i in range(60):
    zc = 0
    oc = 0
    for j in range(len(A)):
        if A[j] % 2 == 0:
            zc += 1
        else:
            oc += 1
        A[j] = A[j] >> 1

    res += zc*oc*2**i
    res %= p

print(res)
### BUGGY CODE ###

from itertools import combinations

N, K=map(int, input().split())
an=list(map(int,input().split()))

if K in an:
    print('POSSIBLE')
    exit()

while True:
    comb=combinations(an,2)
    prean = an[:]
    for it in comb:
        a = abs(it[0] - it[1])
        if a == K:
            print('POSSIBLE')
            exit()
        if a not in an:
          an.append(a)
    if len(an) == len(prean):
        print('IMPOSSIBLE')
        break

### FIXED CODE ###

from functools import reduce
from fractions import gcd

N, K=map(int, input().split())
an=list(map(int,input().split()))

m = max(an)
g = reduce(lambda x, y: gcd(x, y), an)

if K <=m and K % g == 0:
    print ('POSSIBLE')
else:
    print ('IMPOSSIBLE')
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i, s in enumerate(S):
  if ((s == "W") & (i%2 == 0)) or ((s == "B") & (i%2 == 1)):
    ans *= (i - (count*2))
    count += 1
if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans % m)

### FIXED CODE ###

N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i in range(N):
  if S[2*i] == "W":
    ans = ans * ((2*i) - (count*2))%m
    count += 1
  if S[2*i + 1] == "B":
    ans = ans * ((2*i + 1) - (count*2))%m
    count += 1
 
if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans % m)
### BUGGY CODE ###

from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    Ai = [int(x) for x in stdin.readline().rstrip().split()]
    for i in range(N):
        spam = Ai[:]
        del spam[i]
        spam = [0] + spam + [0]
        ham = [abs(spam[i] - spam[i + 1]) for i in range(len(spam) - 1)]
        print(sum(ham))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    Ai = [int(x) for x in stdin.readline().rstrip().split()]

    foo = [0] + Ai + [0]
    bar = [abs(foo[i] - foo[i + 1]) for i in range(len(foo) - 1)]
    sumbar = sum(bar)

    spam = [0] + Ai + [0]
    for i in range(N):
        if foo[i] <= foo[i + 1] <= foo[i + 2] or foo[i + 2] <= foo[i + 1] <= foo[i]:
            print(sumbar)
        else:
            ans = sumbar - (bar[i] + bar[i + 1]) + abs(spam[i] - spam[i + 2])
            print(ans)


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

n = int(input())
a = list(map(int,input().split()))
c = [0]*50
for i in a:
    s = format(i,'b')[::-1]
    for i in range(len(s)):
        c[i] += int(s[i])

buf = []
for i in a:
    s = format(i,'b').zfill(50)[::-1]
    ans = ''
    for i in range(50):
        ans +=  str((c[i]-int(s[i]))%2)
    ans = ans[::-1]
    buf.append(int(ans,2))

print(*buf)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
c = 0
for i in a:
    c ^= i

buf = []
for i in a:
    buf.append(c^i)
    
print(*buf)
### BUGGY CODE ###

num = int(input())
words = []
answer = 0

for i in range(num):
  words.append(sorted(list(input())))
words.sort(key=lambda x:x[0])
for i in range(num):
  q = 0
  for j in range(num -i - 1):
    p = 0
    out = 0
    if q >0 and words[i][0] != words[j + 1 + i][0]:
      break
    for k in range(10):
      if words[i][k] == words[j + 1 + i][k]:
        p += 1
      else:
        break
    if p == 10:
      answer += 1
      q += 1
    
print(answer)


### FIXED CODE ###

import math
num = int(input())
words = {}

for i in range(num):
  a = str(sorted(list(input())))
  
  if a in words:
    words[a] += 1
  else:
  	words[a] = 1

points = list(words.values())
sum = 0
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(len(points)):
  if points[i] > 1:
  	sum += combinations_count(points[i], 2)
print(sum)
### BUGGY CODE ###

n = int(input())
V = list(map(int, input().split()))
A = V[::2]
B = V[1::2]
set_A = set(A)
set_B = set(B)
max_a = 0
max_b = 0

for a in set_A:
  cnt_a = A.count(a)
  max_a = max(max_a, cnt_a)
for b in set_B:
  cnt_b = B.count(b)
  max_b = max(max_b, cnt_b)
ans = (len(A) - max_a) + (len(B) - max_b)
if ans == 0 and A[0] == B[0]:
  ans = n // 2
print(ans)

### FIXED CODE ###

n = int(input())
V = list(map(int, input().split()))
A = {}
B = {}
for i in range(n):
  if i % 2 == 0:#A
    A[V[i]] = A.get(V[i], 0) + 1
  else:#B
    B[V[i]] = B.get(V[i], 0) + 1

A = sorted(A.items(), key=lambda x:x[1], reverse=True)
B = sorted(B.items(), key=lambda x:x[1], reverse=True)
a1, b1 = A[0][1], B[0][1]
am, bm = A[0][0], B[0][0]
ans = n - a1 - b1
if ans == 0 and V[0]==V[1]:
  ans = n//2
elif am == bm and n > 4:
  a2,b2 = A[1][1], B[1][1]
  ans = min(n - a2 - b1, n - a1 - b2) 
print(ans)
### BUGGY CODE ###

N = int(input())
A=list(map(int,input().split()))
s = 1
for i in A:
  s *= i
if s > 10**18:
  s = -1
print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
if 0 in A:
  print(0)
  exit()
prod = 1
for i in A:
  prod *= i
  if prod > 10**18:
    print(-1)
    exit()
print(prod)
### BUGGY CODE ###

#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


mod=998244353
pp=pow(2,mod-2,mod)

n,s=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
dp=[[0 for j in range(s+1)] for i in range(n+1)]
dp[0][0]=pow(2,n,mod)
d=defaultdict(int)

for i in range(n):
    for j in range(s+1):
        if dp[i][j]>=1:
            if j+l[i]<=s:
                dp[i+1][j+l[i]]+=dp[i][j]*pp# +pow(2,n-1,mod)
                dp[i+1][j+l[i]]%=mod
            dp[i+1][j]+=dp[i][j]
print(dp[-1][-1]%mod)


### FIXED CODE ###

#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


mod=998244353
pp=pow(2,mod-2,mod)

n,s=map(int,input().split())
l=list(map(int,input().split()))

dp=[[0 for j in range(s+1)] for i in range(n+1)]
dp[0][0]=pow(2,n,mod)

for i in range(n):
    for j in range(s+1):
        if dp[i][j]>=1:
            if j+l[i]<=s:
                dp[i+1][j+l[i]]+=dp[i][j]*pp# +pow(2,n-1,mod)
                dp[i+1][j+l[i]]%=mod
            dp[i+1][j]+=dp[i][j]
            dp[i+1][j]%=mod
print(dp[-1][-1]%mod)
### BUGGY CODE ###

n=int(input())
hoge=list(map(int,input().split()))
###
def huga(a,b):
  x=max(a,b)
  y=min(a,b)
  z=1
  for i in range(y):
    wa=i+1
    if(x%wa==0 and y%wa==0):
      z=wa
  return z
###
hoge.sort()
ans=hoge[0]
for i in range(n-1):
  ans=huga(ans,hoge[i+1])
  
print(ans)

### FIXED CODE ###

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

n=int(input())
hoge=list(map(int,input().split()))
hoge.sort()
for i in range(n-1):
  hoge[i+1]=gcd(hoge[i],hoge[i+1])
  
print(hoge[-1])
### BUGGY CODE ###

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

def lower_bound(al, key):
    """
    一般に左側が満たしておらず、右側は満たしている判定基準(境目は一つ)ならlower_boundになる
    (条件を満たすもののうち、最小のインデックスを返す)
    単調にさえなっていれば、左右が逆になっていても検索には使える(ng/okも一緒に逆にする必要がある)
    """
    def isOk(a):
        # alの中でkey以上のアイテムのうち最小のインデックスを返す
        # upper_boundにする時にはa>key
        return a>=key

    ng = -1
    ok = len(al)

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

INF = 10**18
a,b,q = map(int, input().split())
sl = [-INF] + [int(input()) for _ in range(a)] + [INF]
tl = [-INF] + [int(input()) for _ in range(b)] + [INF]
# print(sl)
# print(tl)
for _ in range(q):
    x = int(input())
    si = lower_bound(sl,x)
    ti = lower_bound(tl,x)
    # print(x,si,ti)
    res = INF
    for s in [sl[si-1], sl[si]]:
        for t in [tl[ti-1], tl[ti]]:
            res = min(
                res,
                abs(s-x)+abs(t-s),
                abs(t-x)+abs(s-t)
            )
    print(res)


### FIXED CODE ###

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

def lower_bound(al, key):
    """
    一般に左側が満たしておらず、右側は満たしている判定基準(境目は一つ)ならlower_boundになる
    (条件を満たすもののうち、最小のインデックスを返す)
    単調にさえなっていれば、左右が逆になっていても検索には使える(ng/okも一緒に逆にする必要がある)
    """
    def isOk(a):
        # alの中でkey以上のアイテムのうち最小のインデックスを返す
        # upper_boundにする時にはa>key
        return a>=key

    ng = -1
    ok = len(al)

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok


a,b,q = map(int, input().split())
sl = [int(input()) for _ in range(a)]
tl = [int(input()) for _ in range(b)]
xl = [int(input()) for _ in range(q)]
# print(sl)
# print(tl)
for x in xl:
    si = lower_bound(sl,x)
    ti = lower_bound(tl,x)
    # print(x,si,ti)

    ssl = []
    if si==a:
        ssl.append(sl[-1])
    elif si==-1:
        ssl.append(sl[0])
    else:
        ssl.append(sl[si])
        if si>0:
            ssl.append(sl[si-1])
    ttl = []
    if ti==b:
        ttl.append(tl[-1])
    elif ti==-1:
        ttl.append(tl[0])
    else:
        ttl.append(tl[ti])
        if ti>0:
            ttl.append(tl[ti-1])

    res = -1
    for s in ssl:
        for t in ttl:
            if s>=x and t>=x:
                tmp = max(s-x, t-x)
            elif s<x and t<x:
                tmp = max(x-s, x-t)
            elif s>=x>=t:
                tmp = min(
                    2*(s-x)+(x-t),
                    (s-x)+2*(x-t)
                )
            else:
                tmp = min(
                    2*(x-s)+(t-x),
                    (x-s)+2*(t-x)
                )
            if res<0:
                res = tmp
            else:
                res = min(res,tmp)
    print(res)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
for _ in range(Q):
    l,r=map(int,input().split())
    lr_S=S[l-1:r]
    n=r-l
    ans=0
    for i in range(n):
        if lr_S[i]=='A':
            if lr_S[i+1]=='C':
                ans+=1
    print(ans)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
AC=[0]*N

cnt=0
for i in range(N-1):
    if S[i]+S[i+1]=='AC':
        AC[i]=cnt
        cnt+=1
        AC[i+1]=cnt
    else:
        AC[i],AC[i+1]=cnt,cnt

for _ in range(Q):
    l,r=map(int,input().split())
    print(AC[r-1]-AC[l-1])
### BUGGY CODE ###

n=int(input())
s=[input() for _ in range(n)]
s.sort()
s.append("")
a=[]
count=[]
i=0
while i<n:
    a.append(s[i])
    s_count=s.count(s[i])
    count.append(s_count)
    i+=s_count
count_max=max(count)
for i in range(len(a)):
    if count[i]==count_max:
        print(a[i])

### FIXED CODE ###

n=int(input())
s=[input() for _ in range(n)]
s.sort()
s.append("")
a=[]
count=[]
buf=1
count_max=1
for i in range(n):
    s_i=s[i]
    if s_i==s[i+1]:
        buf+=1
    else:
        if buf>=count_max:
            a.append(s_i)
            count.append(buf)
            if buf>count_max:
                count_max=buf
        buf=1
count_max=max(count)
for i in range(len(a)):
    if count[i]==count_max:
        print(a[i])
### BUGGY CODE ###

n = int(input())

ans = 0
for i in range(n):
    ans += i

print(ans)



 

 


                                        




    




        


    







        



### FIXED CODE ###

n = int(input())

print(int(n*(n-1)//2))
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    S = list(input().strip())
    n = len(S)

    ans = 0
    cnt = 0
    for i in range(n):
        if S[i:i+3] == ['A', 'B', 'C']:
            cnt += 1
            S[i] = 'B'
            S[i+1] = 'C'
            S[i+2] = 'A'

    S = S[::-1]
    for i in range(n):
        if S[i:i+3] == ['C', 'B', 'A']:
            cnt += 1
            S[i] = 'A'
            S[i+1] = 'C'
            S[i+2] = 'B'

    ans += cnt
    while cnt > 0:
        cnt = 0
        S = S[::-1]
        for i in range(n):
            if S[i:i+3] == ['A', 'B', 'C']:
                cnt += 1
                S[i] = 'B'
                S[i+1] = 'C'
                S[i+2] = 'A'

        S = S[::-1]
        for i in range(n):
            if S[i:i+3] == ['C', 'B', 'A']:
                cnt += 1
                S[i] = 'A'
                S[i+1] = 'C'
                S[i+2] = 'B'

        ans += cnt


    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    S = input().strip()
    n = len(S)

    T = ''
    i = 0
    while i < n:
        if S[i] == 'A':
            T += 'A'
            i += 1
        elif S[i:i+2] == 'BC':
            T += 'D'
            i += 2
        else:
            T += S[i]
            i += 1

    ans = 0
    cnt = 0
    for c in T:
        if c == 'A':
            cnt += 1
        elif c == 'D':
            ans += cnt
        else:
            cnt = 0

    return ans


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

mod = 1000000007
n = int(input())
a = list(map(int,input().split()))
ans = 0
s = sum(a)
for i in range(n-1):
    b = (s-sum(a[:i+1]))%mod
    ans += (a[i]*(b))%mod
print(ans%mod)

### FIXED CODE ###

mod = 1000000007
n = int(input())
a = list(map(int,input().split()))
ans = 0
b = sum(a)
for i in range(n-1):
    b = b-a[i]
    ans += (a[i]*(b))%mod
print(ans%mod)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))

Devide_N=10**9+7
Rem_2_32_DN=(2**32)%Devide_N

if N%2==1:
  if A.count(0)!=1:
    print(0)
  else:
    for ch_n in range(1,(N-1)//2+1):
      if A.count(ch_n*2)!=2:
        break
      else:
        A.remove(ch_n*2)
        A.remove(ch_n*2)
    else:
      exp=(N-1)//2
      
      exp_quotient_32=exp//32
      exp_rem_32=exp%32
      Rem_ans_Devide_N=1
      for _ in range(exp_quotient_32):
        Rem_ans_Devide_N=(Rem_ans_Devide_N*Rem_2_32_DN)%Devide_N
        
      print((Rem_ans_Devide_N*2**(exp_rem_32))%Devide_N)
      sys.exit()
    print(0)
else:
  for ch_n in range(1,N//2+1):
    if A.count(ch_n*2-1)!=2:
      break
    else:
      A.remove(ch_n*2-1)
      A.remove(ch_n*2-1)
  else:
    exp=N//2
    
    exp_quotient_32=exp//32
    exp_rem_32=exp%32
    Rem_ans_Devide_N=1
    for _ in range(exp_quotient_32):
      Rem_ans_Devide_N=(Rem_ans_Devide_N*Rem_2_32_DN)%Devide_N
      
    print((Rem_ans_Devide_N*2**(exp_rem_32))%Devide_N)
    sys.exit()
  print(0)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
A.sort()
Devide_N=10**9+7
Rem_2_32_DN=(2**32)%Devide_N

if N%2==1:
  if (A[0]!=0 or A[1]==0 if N>2 else A[0]!=0):
    print(0)

  else:
    del A[0]
    for ch_n in range(1,(N-1)//2+1):
      if A[0]!=ch_n*2 or A[1]!=ch_n*2:
        break
      else:
        del A[0:2]
    else:
      exp=(N-1)//2
      
      exp_quotient_32=exp//32
      exp_rem_32=exp%32
      Rem_ans_Devide_N=1
      for _ in range(exp_quotient_32):
        Rem_ans_Devide_N=(Rem_ans_Devide_N*Rem_2_32_DN)%Devide_N
        
      print((Rem_ans_Devide_N*2**(exp_rem_32))%Devide_N)
      sys.exit()
    print(0)

else:
  for ch_n in range(1,N//2+1):
    if A[0]!=ch_n*2-1 or A[1]!=ch_n*2-1:
      break
    else:
      del A[0:2]
  else:
    exp=N//2
    
    exp_quotient_32=exp//32
    exp_rem_32=exp%32
    Rem_ans_Devide_N=1
    for _ in range(exp_quotient_32):
      Rem_ans_Devide_N=(Rem_ans_Devide_N*Rem_2_32_DN)%Devide_N
      
    print((Rem_ans_Devide_N*2**(exp_rem_32))%Devide_N)
    sys.exit()
  print(0)