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

S=input()
T=input()
s=len(S)
t=len(T)
dp=[['' for i in range(t+1)] for j in range(s+1)]
for i in range(s):
    for j in range(t):
        if S[i]!=T[j]:
            dp[i+1][j+1]=dp[i+1][j]
            if len(dp[i][j+1])>len(dp[i+1][j]):
                dp[i+1][j+1]=dp[i][j+1]
            continue
        dp[i+1][j+1]=dp[i][j]+S[i]
print(dp[s][t])


### FIXED CODE ###

S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

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

N = int(input())
S = list(input())

ans = 0
for i in range(1000):
    pw = list("{0:03d}".format(i))

    w1 = -1
    for j in range(N-2):
        if S[j] == pw[0]:
            w1 = j
            break
    if w1 == -1:
        continue

    w2 = -1
    for j in range(w1+1, N-1):
        if S[j] == pw[1]:
            w2 = j
            break
    if w2 == -1:
        continue

    w3 = -1
    for j in range(w2+1, N):
        if S[j] == pw[2]:
            w3 = j
            break
    if w3 == -1:
        continue

    ans += 1

print(ans)


### FIXED CODE ###

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

N = int(input())
S = list(input())

ans = 0
for i in range(1000):
    pw = list("{0:03d}".format(i))

    if pw[0] in S:
        w1 = S.index(pw[0])
        if pw[1] in S[w1+1:]:
            w2 = w1+1 + S[w1+1:].index(pw[1])
            if pw[2] in S[w2+1:]:
                ans += 1

print(ans)
### BUGGY CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(10000000)

class UnionFind:
    def __init__(self, N: int) -> None:
        self.par = [i for i in range(N)]
    
    def root(self, x: int) -> bool:
        if self.par[x] == x: #親が自分自身なら頂点
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        else:
            self.par[rx] = ry
    
    def same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)


def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        uf.unite(a-1, b-1)
    
    g = Counter(uf.root(x) for x in range(N))
    ans = g.most_common(1)[0][1]
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(10000000)

class UnionFind:
    def __init__(self, N: int) -> None:
        #自身が親なら、その集合に属する頂点数に-1をかけたもの
        #自身が親でないなら、自身の親
        self.par = [-1 for i in range(N)]
    
    def root(self, x: int) -> bool:
        if self.par[x] < 0: #親が自分自身なら頂点
            return x
        else:
            #経路圧縮してから返す
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x: int, y: int) -> None:
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        else:
            if rx > ry:
                rx, ry = ry, rx
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
    
    def same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)
    
    def size(self, x: int) -> int:
        root = self.root(x)
        return -self.par[root]


def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, input().split())
        uf.unite(a-1, b-1)
    
    ans = 0
    for i in range(N):
        ans = max(ans, uf.size(i))
    print(ans)

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

N,P=map(int,input().split())
S=str(input())
S=S[::-1]
Si=[]
count=0
sum=0
if P==2:
    for i in range(N):
        if int(S[i])%2==0:
            count+=N-i
elif P==5:
    for i in range(N):
        if S[i]=="0" or S[i]=="5":
            count+=N-i
else:
    listS=[int(i) for i in S]
    mod=[(k*10**j)%P for j,k in enumerate(listS)]
    for m in mod:
        sum+=m
        Si.append(sum%P)
        
    for start in range(N):
        if Si[start]==0:
            count+=1            
        for end in range(start+1,N):
            if Si[start]==Si[end]:
                count+=1
print(count)

### FIXED CODE ###

n, p = map(int, input().split())
 
s = list(input())
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    d = [0] * (n + 1)
    ten = 1
    for i in range(n - 1, -1, -1):
        a = int(s[i]) * ten % p
        ten *= 10
        ten %= p
        d[i - 1] = (d[i] + a) % p
    cnt = [0] * p
    for i in range(n, -1, -1):
        cnt[d[i]] += 1
    for  i in cnt:
        ans+=i*(i-1)/2

print(int(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input())
B=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    
    if 10**4+1-w<=s:
        x=max(DP[10**4+1-w:s+1])+v
        if DP[-1]<x:
            DP[-1]=x
        
    for i in range(min(10**4-w,s),-1,-1):
        if DP[i+w]<DP[i]+v:
            DP[i+w]=DP[i]+v

print(max(DP))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
B=[list(map(int,input().split())) for i in range(N)]

B.sort(key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    for i in range(s,-1,-1):
        if i+w<=10**4:
            if DP[i+w]<DP[i]+v:
                DP[i+w]=DP[i]+v

        else:
            if DP[-1]<DP[i]+v:
                DP[-1]=DP[i]+v

print(max(DP))
### BUGGY CODE ###

S=input()
Q=input()
#rev -1:False 0:True
rev=-1
for i in range(int(Q)):
  tmp=input().split()
  if tmp[0]=='1':
    rev = abs(rev)-1
  else:
    if rev+int(tmp[1])==1:
      S = S + tmp[2]
    else:
      S = tmp[2] + S
if rev==-1:
  print(S)
else:
  print(S[::-1])

### FIXED CODE ###

S=input()
Q=input()
#rev -1:False 0:True
L=''
R=''
rev=-1
for i in range(int(Q)):
  tmp=input().split()
  if tmp[0]=='1':
    rev = abs(rev)-1
  else:
    if rev+int(tmp[1])==1:
      R = R + tmp[2]
    else:
      L = L + tmp[2]
if rev==-1:
  print(L[::-1]+S+R)
else:
  print(R[::-1]+S[::-1]+L)
### BUGGY CODE ###

n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
res=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,a[i][0]-1,-1):
        res[j]=max(res[j],res[j-a[i][0]]+a[i][1])
print(res[w])

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
res=[0 for _ in range(w+1)]
for i in range(n):
    for j in range(w,a[i][0]-1,-1):
        res[j]=max(res[j],res[j-a[i][0]]+a[i][1])
print(res[w])
### BUGGY CODE ###

import itertools
import collections
N = int(input())
A = [int(_) for _ in input().split()]
c = sorted(collections.Counter(A).values())
acc = list(itertools.accumulate([0] + c))
n = len(acc) - 1
for i in range(1, n + 1):
    r = 0
    j = 0
    while i - j > 0:
        if (i - j) * c[-1 - j] <= acc[-1 - j]:
            r = acc[-1 - j] // (i - j)
            break
        else:
            j += 1
    print(r)
for _ in range(N - n):
    print(0)


### FIXED CODE ###

import itertools
import collections
N = int(input())
A = [int(_) for _ in input().split()]
c = sorted(collections.Counter(A).values())
acc = list(itertools.accumulate([0] + c))
n = len(acc) - 1
j = 0
for i in range(1, n + 1):
    r = 0
    while i - j > 0:
        if (i - j) * c[-1 - j] <= acc[-1 - j]:
            r = acc[-1 - j] // (i - j)
            break
        else:
            j += 1
    print(r)
for _ in range(N - n):
    print(0)
### BUGGY CODE ###

import math
n, m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))

for i in range(m):
    max = 0
    for j in range(n):
        if a[j] > max:
            max = a[j]
            maxIndex = j
    a[maxIndex] /= 2

count = 0
for i in range(n):
    count += math.floor(a[i])

print(count)


### FIXED CODE ###

import math
import heapq

n, m = map(int, input().split(" "))
a = list(map(int, input().split(" ")))

a_minus = [a[i] * (-1) for i in range(n)]

heapq.heapify(a_minus)

for i in range(m):
    value = heapq.heappop(a_minus)
    value /= 2
    heapq.heappush(a_minus, value)

count = 0
for i in range(n):
    value = heapq.heappop(a_minus) * -1
    count += math.floor(value)

print(count)
### BUGGY CODE ###

import sys

n, m = map(int, input().split())

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

gap = []


if( n >= m):
    print(0)
    sys.exit()
else:
    x = sorted(x)
    for i in range(m-1):
        gap.append(x[i+1] - x[i])
        gaps = sorted(gap)



print(sum(gaps[:m-n]))


### FIXED CODE ###

import sys

n, m = map(int, input().split())

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

gap = []


if( n >= m):
    print(0)
    sys.exit()
else:
    x = sorted(x)
    for i in range(m-1):
        gap.append(x[i+1] - x[i])
    gaps = sorted(gap)

print(sum(gaps[:m-n]))
### BUGGY CODE ###

original = input()[::-1]

target = 2019

# s = reversed(original)
s = original

counts = [0] * 2019
counts[0] = 1

digit = 1
mod = 0
for c in s:
    val = int(c) * digit
    currentMod = val % target
    mod = (currentMod + mod) % target
    digit *= 10

    counts[mod] += 1
    # count = countOfMod.get(mod, 0) + 1
    # countOfMod[mod] = count
    # if countOfMod[mod] > 1:
    #     results.setdefault(mod, int(count*(count-1)/2))

# print(sum(results.values()))

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans)  # 答えの出力

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans)
### BUGGY CODE ###

def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

def isOK(index,key,li):
    if li[index] >= key:
        #不等号にイコールを入れないとokはliの中でkey以下の数字がいくつあるかを表し、
        #ここの不等号にイコールを入れると
        #okはliの中でkey未満の数字がいくつあるかを表すようになる
        return True
    else:
        return False
def binary_search(key,li):
    ng = -1
    ok = len(li)
    while abs(ok - ng) > 1:
        mid = ok + ng //2
        if isOK(mid,key,li):
            ok = mid
        else:
            ng = mid
    return ok
    #liはsortしておくことに注意


def isOK2(index,key,li):
    if li[index] > key:
        #不等号にイコールを入れないとokはliの中でkey以下の数字がいくつあるかを表し、
        #ここの不等号にイコールを入れると
        #okはliの中でkey未満の数字がいくつあるかを表すようになる
        return True
    else:
        return False
def binary_search2(key,li):
    ng = -1
    ok = len(li)
    while abs(ok - ng) > 1:
        mid = ok + ng //2
        if isOK2(mid,key,li):
            ok = mid
        else:
            ng = mid
    return ok
    #liはsortしておくことに注意
n = I()
a_li = sorted(LI())
b_li = sorted(LI())
c_li= sorted(LI())
ans = 0
for i in range(n):
    B = b_li[i]
    k = n - binary_search2(B,c_li)
    l = binary_search(B,a_li)
    ans += k*l
print(ans)


### FIXED CODE ###

import bisect

def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
n = I()
a_li = sorted(LI())
b_li = sorted(LI())
c_li= sorted(LI())
ans = 0
for i in range(n):
  B = b_li[i]
  k = n - bisect.bisect_right(c_li,B)
  l = bisect.bisect_left(a_li,B)
  ans += k*l
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(range(1,n+1))
for i in range(m):
	b=list(map(int,input().split()))
	c=list(range(b[0],b[1]+1))
	a=list(set(c) & set(a))
print(len(list(a)))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(range(1,n+1))
l=0
l1=0
r=0
r1=10**10

for i in range(m):
	l,r=map(int,input().split())
	if l>l1:
		l1=l
	if r<r1:
		r1=r
b=list(range(l1,r1+1))
a=list(set(b) & set(a))
print(len(list(a)))
### BUGGY CODE ###

s = input()
q = int(input())

flag = True
ans = s
for i in range(q):
  query = list(input().split())
  if int(query[0]) == 1:
    flag = not flag
  else:
    if int(query[1]) == 1:
      if flag:
        ans = query[2] + ans
      else:
        ans+=query[2]
    else:
      if flag:
        ans+=query[2]
      else:
        ans = query[2] + ans

if flag:
  print("".join(ans))
else:
  t = ans[::-1]
  print("".join(t))



### FIXED CODE ###

s = input()
q = int(input())
revFlag = False
head, tail = [], []

for i in range(q):
  query = list(input().split())
  if int(query[0]) == 1:
    revFlag = not revFlag
  else:
    if int(query[1]) == 1:
      if not revFlag:
        head.append(query[2])
      else:
        tail.append(query[2])
    else:
      if not revFlag:
        tail.append(query[2])
      else:
        head.append(query[2])

if not revFlag:
  h = "".join(reversed(head))
  t = "".join(tail)
  print("".join([h, s, t]))
else:
  h = "".join(head)
  t = "".join(reversed(tail))
  print("".join([t, s[::-1], h]))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N)]
    edge = {}
    ans_key = []
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge[(a-1, b-1)] = -1
        ans_key.append((a-1, b-1))
    max_g = max(len(g) for g in G)

    def dfs(max_g):
        todo = [0]
        seen = [False]*N
        seen[0] = True
        color = [{i+1 for i in range(max_g)} for _ in range(N)]
        par = [-1]*N
        while todo:
            u = todo.pop()
            if par[u] != -1:
                if par[u] < u:
                    color[u].discard(edge[(par[u], u)])
                else:
                    color[u].discard(edge[(u, par[u])])
            for v in G[u]:
                if seen[v]:
                    continue
                seen[v] = True
                todo.append(v)
                c = color[u].pop()
                par[v] = u
                if u < v:
                    edge[(u, v)] = c
                else:
                    edge[(v, u)] = c

    dfs(max_g)
    print(max_g)
    for k in ans_key:
        print(edge[k])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    G = [[]*N for _ in range(N)]
    edge_color = {}
    key_ = []
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
        edge_color[(a-1, b-1)] = -1
        key_.append((a-1, b-1))
    from collections import deque
    deg_max = 0
    for g in G:
        deg_max = max(deg_max, len(g))

    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(s):
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            if G_parent[u] == 'NIL':
                now_color = 1
            else:
                now_color = (edge_color[(G_parent[u], u)] + 1) % deg_max
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    Q.append(v)
                    edge_color[(u, v)] = now_color % deg_max
                    now_color += 1
            G_color[u] = 'BLACK'
    bfs(0)
    print(deg_max)
    for k in key_:
        print(edge_color[k]+1)


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

S = int(input())
count = 0
l = [0]*2019
key = range(2019)
l[0] = 1
d = dict(zip(key,l))

for i in range(1,len(str(S))+1):
    n =((S%10**i)%2019)
    d[n] += 1
    

for j in range(2019):
    if d[j] >= 2:
        count += d[j]*(d[j]-1)//2

print(count)


### FIXED CODE ###

S = input()
count = 0
l = [0]*2019
l[0] = 1
mod = 2019
tmp = 0

for i in range(1,len(S)+1):
    tmp = (tmp + int(S[len(S)-i])*pow(10,i-1,mod))%mod
    l[tmp] += 1
    

for j in range(2019):
    if l[j] >= 2:
        count += l[j]*(l[j]-1)//2

print(count)
### BUGGY CODE ###

import itertools

def main():
    n = int(input())
    l = sorted(list(map(int, input().split())), reverse=True)
    count = 0
    for i in range(n-2):
        a = l[i]
        for j in range(i+1,n-1):
            b = l[j]
            x = a-b
            z = a+b
            for k in range(j+1, n):
                c = l[k]
                if x >= c:
                    break
                if c < z:
                    count += 1
    print(count)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect

def main():
    n = int(input())
    l = sorted(list(map(int, input().split())))
    count = 0
    for i in range(n-2):
        a = l[i]
        for j in range(i+1, n-1):
            b = l[j]
            kmax = bisect.bisect_left(l, a+b)
            #print("k", kmax, "j", j, "k-j", kmax-(j+1), a, b)
            count += max(kmax-(j+1),0)
    print(count)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,K = map(int, input().split())
A = [int(x)-1 for x in map(int, input().split())]

l = []
place = 0
while True:
    if K==0:
        print(place+1)
        exit()
    l.append(place)
    place = A[place]
    K -= 1
    if place in l:
        s = place
        break

l=[]
count = 0
while True:
    l.append(place)
    place = A[place]
    count += 1
    if place == s:
        break
print(l[K%count]+1)



### FIXED CODE ###

N,K = map(int, input().split())
A = [int(x)-1 for x in map(int, input().split())]
flag = [False]*N
l = []
place = 0
while True:
    if K==0:
        print(place+1)
        exit()
    l.append(place)
    flag[place]=True
    place = A[place]
    K -= 1
    if flag[place]:
        ind = l.index(place)
        count = len(l) - ind
        print(l[ind + K%count]+1)
        exit()
### BUGGY CODE ###

K,S=map(int,input().split())

cnt=0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if S==(x+y+z):
                cnt+=1

print(cnt)



### FIXED CODE ###

K,S=map(int,input().split())

cnt=0
for x in range(K+1):
    for y in range(K+1):
        if 0<=(S-(x+y))<=K:
            cnt+=1

print(cnt)
### BUGGY CODE ###

import array
import sys
def counting_sort(A, B, n, k=10000):
    C = array.array('I', [0 for i in range(k+1)])
    for j in range(0, n):
        x = A[j]
        C[x] += 1
    for i in range(0, k+1):
        C[i] += C[i - 1]
    for j in range(n - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1

n = int(input())
A = list(map(int , sys.stdin.readline()[:-1].split()))

B = array.array("I", [0 for i in range(n)])
for k in A:
    counting_sort(A, B, n)

print(*B)

### FIXED CODE ###

import array
import sys
def counting_sort(A, B, n, k=10000):
    C = array.array('I', [0 for i in range(k+1)])
    for j in range(0, n):
        x = A[j]
        C[x] += 1
    for i in range(0, k+1):
        C[i] += C[i - 1]
    for j in range(n - 1, -1, -1):
        B[C[A[j]] - 1] = A[j]
        C[A[j]] -= 1

n = int(input())
A = list(map(int , sys.stdin.readline()[:-1].split()))

B = array.array("I", [0 for i in range(n)])
counting_sort(A, B, n)

print(*B)
### BUGGY CODE ###

N = int(input())
L = sorted([int(i) for i in input().split()])
count = 0

for j in range(N):
    for k in range(j + 1,N):
        right = L[j] + L[k]
        left = abs(L[j] - L[k])
        for l in range(k + 1,N):
            if(L[l] < right and L[l] > left):
                count += 1

print(count) 

### FIXED CODE ###

N = int(input())
L = sorted([int(i) for i in input().split()])
count = 0

from bisect import bisect_left as bi

for j in range(N):
    for k in range(j + 1,N - 1):
        right = L[j] + L[k]
        ite_right = bi(L,right)
        count = count + (ite_right - k - 1)

print(count)
### BUGGY CODE ###

from itertools import product

n = int(input())
s = input()
r, g, b = [], [], []

for i, char in enumerate(s):
    if char == 'R': r.append(i)
    elif char == 'G': g.append(i)
    else: b.append(i)

count = 0
# for config in product(r,g,b):
#     a, b, c = config
#     a, b, c = sorted((a, b, c))

#     if (b-a)!=(c-b): count += 1

# print(count)

for i in r:
    for j in g:
        for k in b:
            if i<j<k:
                if (j-i)!=(k-j): count += 1
            if j<i<k:
                if (i-j)!=(k-i): count += 1
            if k<i<j:
                if (i-k)!=(j-i): count += 1
            if i<k<j:
                if (k-i)!=(j-k): count += 1
            if j<k<i:
                if (k-j)!=(i-k): count += 1
            if k<j<i:
                if (j-k)!=(i-j): count += 1
            

print(count)


### FIXED CODE ###

n = int(input())
s = input()

rinds, ginds, binds = [], [], []

for i in range(n):
    if s[i] == 'R': rinds.append(i)
    elif s[i] == 'G': ginds.append(i)
    else: binds.append(i)


rlen, glen, blen = len(rinds), len(ginds), len(binds)

def binsearch_same(binds, blen, dist, i):
    lo, hi = 0, blen-1
    while lo<=hi:
        mid = lo + (hi-lo)//2
        d = binds[mid] - i
        if dist == d:
            return True
        elif d < dist:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

ans = 0

for i in rinds:
    for j in ginds:
        dist = abs(i-j)
        i_ = min(i, j)
        j_ = max(i, j)
        ans += blen
        # i' < j' < k

        if binsearch_same(binds, blen, dist, j_):
            ans -= 1
        # i'< k < j' 
        if dist%2==0 and binsearch_same(binds, blen, dist//2, i_):
            ans -= 1
        # # k < i' < j'
        if binsearch_same(binds, blen, -dist, i_):
            ans -= 1

print(ans)
### BUGGY CODE ###

def f(x):
    div = 1
    while div * div <= x:
        if x % div == 0:
            for a in range(0, div + 1):
                b = a - div
                if a ** 5 - b ** 5 == x:
                    return a, b

            opp_div = x // div
            for a in range(0, opp_div + 1):
                b = a - opp_div
                if a ** 5 - b ** 5 == x:
                    return a, b
        div += 1


def main():
    x = int(input())
    a, b = f(x)
    print(a, b)


main()


### FIXED CODE ###

def f(x):
    div = 1
    while div * div <= x:
        if x % div == 0:
            for a in range(0, int((x // div) ** 0.25) + 2):
                b = a - div
                if a ** 5 - b ** 5 == x:
                    return a, b

            opp_div = x // div
            for a in range(0, int((x // opp_div) ** 0.25) + 2):
                b = a - opp_div
                if a ** 5 - b ** 5 == x:
                    return a, b
        div += 1


def main():
    x = int(input())
    a, b = f(x)
    print(a, b)


main()
### BUGGY CODE ###

import sys
n = input()
l = list(map(int,input().split()))
if 0 in l:
    print(0)
    sys.exit()
result = 1
for i in l:
    result *= i
if result > 1000000000000000000:
    print(-1)
else:
    print(result)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    if 0 in A:
        print(0)
        return
    result = 1
    for a in A:
        result *= a
        if result > 10**18:
            print(-1)
            return
    print(result)

main()