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

import sys
from collections import deque
import fractions
from functools import reduce
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

from collections import deque


def bfs(sx, sy, gx, gy, H, W):
    d = [[-1 for i in range(W)] for j in range(H)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break
        for i in range(4):
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            #print(nx, ny)
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != "#" and d[ny][nx] == -1:
                que.append((ny, nx))
                #print(p[0], p[1], ny, nx)
                d[ny][nx] = d[p[0]][p[1]] + 1
    return d[gy][gx]


H, W = na()
ans = 0
maze = [input() for i in range(H)]
fin = []
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        for gy in range(H):
            for gx in range(W):
                if maze[gy][gx] == '#':
                    continue
                if (gx, gy, sx, sy) in fin:
                    continue
                else:
                    #print(sx, sy, gx, gy)
                    fin.append((sx, sy, gx, gy))
                    ans = max(ans, bfs(sx, sy, gx, gy, H, W))
                    #print(ans)
print(ans)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
s = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]
ans = 0

for y in range(1, H+1):
    for x in range(1, W+1):
        if s[y][x] == '#':
            continue
        visited = [[0]*(W+2) for _ in range(H+2)]
        visited[y][x] = 1
        max_s = 0
        dq = deque([(y, x, 0)])

        while dq:
            cy, cx, steps = dq.popleft()
            if steps > max_s:
                max_s = steps
            steps += 1

            for dy, dx in ((cy+1, cx), (cy-1, cx), (cy, cx+1), (cy, cx-1)):
                if s[dy][dx] == '#' or visited[dy][dx]:
                    continue
                visited[dy][dx] = 1
                dq.append((dy, dx, steps))

        ans = max(ans, max_s)

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

import numpy as np
from scipy.sparse import coo_matrix

n, m = map(int, input().split())
a = np.empty(m, dtype=np.int)
b = np.empty(m, dtype=np.int)
for i in range(m):
    a[i], b[i] = map(lambda x: int(x)-1, input().split())

g = coo_matrix((np.ones(m, dtype=np.int8), (a, b)), (n, n)).tolil()
res = 'IMPOSSIBLE'
for i in range(n):
    if g[i, n-1] == 0:
        continue
    if g[0, i] == 1:
        res = 'POSSIBLE'
        break

print(res)


### FIXED CODE ###

import numpy as np

n, m = map(int, input().split())
from_1 = np.zeros(n+1, dtype=np.int)
to_n = np.zeros(n+1, dtype=np.int)
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        from_1[b] = 1
    elif b == n:
        to_n[a] = 1

print('IMPOSSIBLE') if np.sum(from_1*to_n) == 0 else print('POSSIBLE')
### BUGGY CODE ###

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    ans = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
            d[j] = min(d[j],d[v]+cost[v][j])
            if d[j] >= d[v]+cost[v][j]:
                ans[j] = v+1
    return ans 


n,w = map(int,input().split()) #n:頂点数　w:辺の数

cost = [[float("inf") for i in range(n)] for i in range(n)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(w):
    x,y = map(int,input().split())
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1
ans = dijkstra(0,n,w,cost)

print('Yes')
for ans in ans[1:]:
    print(ans)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
c = [[] for _ in range(n)]  # 隣接してる部屋リスト
ans = [-1]*n
ans[0] = 0
for _ in range(m):
    a,b = map(int, input().split())
    c[a-1].append(b-1)
    c[b-1].append(a-1)

d = deque([0])  # 0だけ入れたdequeを作成

while d:
    cur = d.pop()
    for x in c[cur]:
        if ans[x]<0:
            ans[x] = cur
            d.appendleft(x)  # curに隣接してる部屋xを次に見ていく
            
print('Yes')
for ans in ans[1:]:
    print(ans+1)
### BUGGY CODE ###

N,A,B=map(int, input().split())
C=0
D=int(N/(A+B))
 
for i in range(D):
	C+=A
	N=N-(A+B)
if N>=A:
	C+=A
else:
	C+=N
print(C)

### FIXED CODE ###

N,A,B=map(int, input().split())
ans=N//(A+B)*A
i=N%(A+B)
ans+=min(i,A)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
*h, = map(int, input().split())

dp = [0] * N
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
    c = 10**10
    for j in range(i - 1, max(i - K - 1, -1), -1):
        t = abs(h[j] - h[i]) + dp[j]
        if t < c:
            c = t
    dp[i] = c
print(dp[N - 1])


### FIXED CODE ###

N, K = map(int, input().split())
*h, = map(int, input().split())

dp = [0] * N
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
    c = 10**10
    for j in range(i - 1, max(i - K - 1, -1), -1):
        t = abs(h[j] - h[i]) + dp[j]
        if t < c:
            c = t
    dp[i] = c
print(dp[N - 1])
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    import bisect 
    n = int(input())
    l = list(map(int,input().split()))
    l1 = []
    for i in range(n):
        l1.append([l[i],i])
    l1.sort(reverse=True)
    ans = 0
    s = [-1,-1,l1[0][1],n,n]

    for i in range(1,n):
        now = bisect.bisect_right(s,l1[i][1])
        count = (s[now-1]-s[now-2])*(s[now]-l1[i][1]) + (s[now+1]-s[now])*(l1[i][1]-s[now-1])
        s.insert(now,l1[i][1])
        ans += count*(n-i)
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
id=[0]*(n+1)
for i,p_i in enumerate(p):
    id[p_i]=i

r = list(range(1,n+1))+[n,n]
l = list(range(-1,n-1))+[-1,-1]
ans=0
for p in range(1,n+1):
    x=id[p]
    r1=r[x]
    r2=r[r1]
    l1=l[x]
    l2=l[l1]
    ans+=p*((x-l1)*(r2-r1) + (l1-l2)*(r1-x))
    r[l1]=r1
    l[r1]=l1
print(ans)
### BUGGY CODE ###

from fractions import gcd

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

a = 1
for i in range(N):
    a = a * A[i] // gcd(a, A[i])

MOD = int(1e9) + 7
sum_ = 0
for v in A:
    sum_ += a // v
    sum_ %= MOD

print(sum_)

### FIXED CODE ###

from fractions import gcd
import sys

if True:
    N, *A = map(int, sys.stdin.read().split())
else:
    N = int(input())
    A = list(map(int, input().split()))

a = 1
for v in A:
    a = a * v // gcd(a, v)

MOD = int(1e9) + 7
sum_ = 0
for v in A:
    sum_ += a // v

print(sum_ % MOD)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.reverse()
step = 0
ans = 0
for i in range(N):
    for j in range(i, N):
        if A[i] - A[j] > 0:
            step = A[i] - A[j]
            ans = max(ans, step)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(1, N):
    if A[i-1] <= A[i]:
        continue
    ans += A[i-1] - A[i]
    A[i] = A[i-1]
print(ans)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
c = 0
for i in range(n//r+1):
  for j in range(n//g+1):
    k = (n-i*r-j*g)
    if k%b == 0 and k >= 0:
      c += 1
print(c)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
c = 0
for i in range(n//r+1):
  for j in range((n-i*r)//g+1):
    k = (n-i*r-j*g)
    if k%b == 0 and k >= 0:
      c += 1
print(c)
### BUGGY CODE ###

n = int(input())
s = []

for i in range(1, n):
    k = n%i
    if k == 0:
        s.append(i+n//i-2)
    
print(min(s))

### FIXED CODE ###

import math

n = int(input())
r_n = int(math.sqrt(n))
s = []

for i in range(1, r_n+1):
    if n%i == 0:
        s.append(n//i + i - 2)
print(min(s))
### BUGGY CODE ###

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

answer = 65535
max_A = max(A)
for x in range(-max_A-1, max_A+1):
    answer = min(answer, sum([abs(num - (i+1) - x) for i, num in enumerate(A)]))

print(answer)

### FIXED CODE ###

import statistics

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

tmp = [num - (i+1) for i, num in enumerate(A)]
med = int(statistics.median(tmp))
answer = sum([abs(num - med) for num in tmp])

print(answer)
### BUGGY CODE ###

def func(x,y,z):
    return x**2+y**2+z**2+x*y+y*z+z*x

n = int(input())

ans = 0
arr = []
for x in range(1,100):
    for y in range(1,100):
        for z in range(1,100):
            ans = func(x,y,z)
            arr.append(ans)
            if ans > n:
                break
for i in range(n):
    print(arr.count(i+1))

### FIXED CODE ###

import itertools
import math
import collections
def main():
    n = int(input())
    s = int(math.sqrt(n))
    a = list(itertools.product(range(1,s),repeat=3))
    ans = []
    for i in range(len(a)):
        t = a[i][0] ** 2 + a[i][1] ** 2 + a[i][2] ** 2 + a[i][0] * a[i][1] + a[i][1] * a[i][2] + a[i][2] * a[i][0]
        ans.append(t)
        # print(ans)
    c = collections.Counter(ans)
    for i in range(1,n+1):
        print(c[i])
        
        
main()
### BUGGY CODE ###

from collections import defaultdict as dd
N = int(input())
S = []
for i in range(N):
    s = input()
    s = sorted(s)
    s = ''.join(s)
    S.append(s)
S.sort()
SS = sorted(list(set(S)))
SN = []
for i in range(len(SS)):
    SN.append(S.count(SS[i]))
    if i < len(SS) - 1:
        j = S.index(SS[i+1])
        S = S[j:]


res = 0
for sn in SN:
    res += sn * (sn - 1) // 2

print(res)

### FIXED CODE ###

def main():
    N = int(input())
    S = []
    for i in range(N):
        s = input()
        s = sorted(s)
        s = ''.join(s)
        S.append(s)
    S.sort()
    SS = sorted(list(set(S)))
    SN = []
    M = len(SS)
    l = 0
    r = len(S)
    for i in range(M):
        for j in range(l, r):
            if S[j] != SS[i]:
                r = j
                break
        SN.append(r - l)
        l = r
        r = len(S)        

    res = 0
    for sn in SN:
        res += sn * (sn - 1) // 2

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

import numpy as np
import math
import copy 
N = input()
N = np.int64(N)
# print(np.sqrt(N))
l = []
x  = 2
while N>1:
    if N%x ==0:
        l.append(x)
        N = N/x
    else:
        x = x + 1
        if x > np.sqrt(N):
            l.append(int(N))
            break
# l = [2, 2, 2, 3, 3, 3, 5, 5, 5, 6079, 6079]
# l = [2, 2, 2, 3]
l2 = []
while l!=[]:
#     print(l)
    i = l[0]
    n = l.count(i)
    l = l[n:]
    l2.append(n)
    if l==[]:break
# print(l2)
# print('///')

i = 0
m = 0
l2 = np.array(l2)
# print(l2)
ans = 0
while True:
    i += 1
#     m = m + i
#     print(m)
    l2 = l2-i
    l2 = l2[l2>=0]
    ans = ans + len(l2)
#     print(l2)
    if len(l2)==0:break
print(ans)

### FIXED CODE ###

import numpy as np
import math
import copy 
N = input()
N = np.int64(N)
# print(np.sqrt(N))
l = []
x  = 2
xen = np.sqrt(N)
while N>1:
    if N%x ==0:
        l.append(x)
        N = N/x
    else:
        x = x + 1
        if x > xen:
            l.append(int(N))
            break
# l = [2, 2, 2, 3, 3, 3, 5, 5, 5, 6079, 6079]
# l = [2, 2, 2, 3]
l2 = []
while l!=[]:
#     print(l)
    i = l[0]
    n = l.count(i)
    l = l[n:]
    l2.append(n)
    if l==[]:break
# print(l2)
# print('///')

i = 0
m = 0
l2 = np.array(l2)
# print(l2)
ans = 0
while True:
    i += 1
#     m = m + i
#     print(m)
    l2 = l2-i
    l2 = l2[l2>=0]
    ans = ans + len(l2)
#     print(l2)
    if len(l2)==0:break
print(ans)
### BUGGY CODE ###

import numpy as np


def solve(n, k, aaa, fff):
    aaa = np.sort(aaa)
    fff = np.sort(fff)[::-1]

    l = 0
    r = 10 ** 12 + 1
    while l < r - 1:
        m = (l + r) // 2
        req = np.clip(aaa - m // fff, 0, None).sum()
        # print(aaa, m // fff, m, req)
        if req > k:
            l = m + 1
        else:
            r = m + 1
    return l


n, k = list(map(int, input().split()))
aaa = np.array(list(map(int, input().split())), dtype=np.int64)
fff = np.array(list(map(int, input().split())), dtype=np.int64)

print(solve(n, k, aaa, fff))


### FIXED CODE ###

import numpy as np


def solve(n, k, aaa, fff):
    aaa = np.sort(aaa)
    fff = np.sort(fff)[::-1]

    l = 0
    r = 10 ** 12
    while l <= r:
        m = (l + r) // 2
        req = np.clip(aaa - m // fff, 0, None).sum()
        # print(aaa, m // fff, m, req)
        if req > k:
            l = m + 1
        else:
            r = m - 1
    return l


n, k = list(map(int, input().split()))
aaa = np.array(list(map(int, input().split())), dtype=np.int64)
fff = np.array(list(map(int, input().split())), dtype=np.int64)

print(solve(n, k, aaa, fff))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
result = 0
mod = 10 ** 9 +7
for i in range(N):
  result = (result + A[i] * sum(A[i+1:]) % mod) % mod
print(result % mod)

### FIXED CODE ###

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

mod = 10 ** 9 +7
amount = sum(A)
calc = []
for i in range(N - 1):
  amount = amount - A[i]
  calc.append(amount)

for i in range(N - 1):
  calc[i] *= A[i]

print(sum(calc) % mod)
### BUGGY CODE ###

n, k = map(int, input().split())
s = [i for i in input()]
zero_one = []
if s[0] == "0":
    zero_one.append(0)
s_ = s[0]
cnt = 0
for i in range(n):
    if s_ == s[i]:
        cnt += 1
    else:
        zero_one.append(cnt)
        cnt = 1
        s_ = s[i]
zero_one.append(cnt)
if s[-1] == "0":
    zero_one.append(0)
ans = 0
l = len(zero_one)
for i in range(0, l, 2):
    ans = max(ans, sum(zero_one[i:i+2*k+1]))
print(ans)

### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
s = [i for i in input()]
zero_one = [0]
if s[0] == "0":
    zero_one.append(0)
s_ = s[0]
cnt = 0
for i in range(n):
    if s_ == s[i]:
        cnt += 1
    else:
        zero_one.append(cnt)
        cnt = 1
        s_ = s[i]
zero_one.append(cnt)
if s[-1] == "0":
    zero_one.append(0)
ans = 0
l = len(zero_one)
zero_one = list(accumulate(zero_one))
for i in range(0, l, 2):
    ans = max(ans, zero_one[min(l-1, i+2*k+1)] - zero_one[i])
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
B=[0]*N
for i in range(M):
    l,r=map(int,input().split())
    for j in range(l-1,r):
        B[j]+=1
print(B.count(M))

### FIXED CODE ###

N,M=map(int,input().split())
ml=0
mh=N
for i in range(M):
    l,r=map(int,input().split())
    ml=max(ml,l)
    mh=min(mh,r)
print(max(0,mh-ml+1))
### BUGGY CODE ###

from sys import stdin
from sys import setrecursionlimit
from collections import Counter
setrecursionlimit(1000000)

# INF = float('inf')
INF = int(1e10)

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    cA = Counter(A)

    for ai in A:
        cA[ai] -= 1
        count = 0
        for key in cA:
            v = cA[key]
            count += (v * (v - 1)) // 2
        cA[ai] += 1
        print(count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from sys import stdin
from sys import setrecursionlimit
from collections import Counter
setrecursionlimit(1000000)

# INF = float('inf')
INF = int(1e10)

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    cA = Counter(A)

    diff = {}
    total = 0
    for key in cA:
        v = cA[key]
        total += (v * (v - 1)) // 2
        diff[key] = (v - 1) * (v - 2) // 2 - (v * (v - 1)) // 2

    for ai in A:
        print(total + diff[ai])
        # cA[ai] -= 1
        # count = 0
        # for key in cA:
        #     v = cA[key]
        #     count += (v * (v - 1)) // 2
        # cA[ai] += 1
        # print(count)

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

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

from collections import defaultdict, deque

S = input()
X, Y = map(int, input().split())
# [x][y][現在の移動距離][現在の向き]をメモする
memo = defaultdict(lambda :defaultdict(lambda :defaultdict(lambda :defaultdict(int))))
len_F = S.count('F')
# ゴールまでの距離と進む予定の距離の偶奇が違えば論外
if (X + Y) % 2 != len_F % 2:
    print('No')
    exit()

def bfs():
    que = deque()
    que.append([0,0,0,'r',len_F])
    while len(que) != 0:
        x, y, cur, dirc, rest = que.popleft()
        # 訪問済
        if memo[x][y][cur][dirc] == 1:
            continue
        memo[x][y][cur][dirc] = 1
        # もうゴールに届かない場合
        if rest < abs(X-x) + abs(Y-y):
            continue
        # 最後までいった時
        if cur == len(S):
            if x == X and y == Y:
                break
            else:
                continue
        # まっすぐ
        if S[cur] == 'F':
            if dirc == 'r': x += 1
            elif dirc == 'l': x -= 1
            elif dirc == 'u': y += 1
            elif dirc == 'd': y -= 1
            que.append([x,y,cur+1,dirc,rest-1])
        # 曲がる
        elif S[cur] == 'T':
            if dirc == 'r' or dirc == 'l':
                que.append([x,y,cur+1,'u',rest])
                que.append([x,y,cur+1,'d',rest])
            elif dirc == 'u' or dirc == 'd': 
                que.append([x,y,cur+1,'r',rest])
                que.append([x,y,cur+1,'l',rest])

bfs()
if any(memo[X][Y][len(S)]):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

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

"""
参考：https://img.atcoder.jp/abc082/editorial.pdf
　　　https://atcoder.jp/contests/abc082/submissions/3930644
・メモリ節約のため、dictをsetにした。
・さらに使い終わった1つ前はもういらないので消すことにした。
"""

S = input()
X, Y = map(int, input().split())

S2 = []
tmp = 0
# 連続するF毎にまとまるように文字列Sを変形させる
for i in range(len(S)):
    if S[i] == 'F':
        tmp += 1
    # T毎に区切る
    else:
        S2.append(tmp)
        tmp = 0
S2.append(tmp)

# 文字列がFのみだとこの後のDPできないので別処理
if len(S2) == 1:
    if X == S2[0] and Y == 0:
        print('Yes')
    else:
        print('No')
    exit()

# あるかないか分かればいいので、dictじゃなくてsetにする
dpx = [set() for _ in range(len(S2))]
dpy = [set() for _ in range(len(S2))]
# xの初期化：step0は右移動、step1ではそのまま
dpx[0].add(S2[0])
dpx[1].add(S2[0])
# yの初期化：step0は何もなし、step1で上下どちらかに移動
dpy[0].add(0)
dpy[1].add(S2[1])
dpy[1].add(-S2[1])
for i in range(2, len(S2)):
    # 左右に移動する
    for v in dpx[i-1]:
        if i % 2 == 0:
            # 到達可能な位置から+-した位置に送る
            dpx[i].add(v-S2[i])
            dpx[i].add(v+S2[i])
        else:
            # yをやる時はxはそのまま
            dpx[i].add(v)
    # 1つ前は使い終わったので削除
    dpx[i-1] = set()
    # 上下に移動する
    for v in dpy[i-1]:
        if i % 2 == 1:
            dpy[i].add(v-S2[i])
            dpy[i].add(v+S2[i])
        else:
            dpy[i].add(v)
    dpy[i-1] = set()
# 最後のstepでXとYが到達可能ならOK
if X in dpx[len(S2)-1] and Y in dpy[len(S2)-1]:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import numpy as np

N = int(input())
L = list(map(int, input().split()))
X = []
for i in range(len(L)):
    X.append(L.index(i+1)+1)
print(*X)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
b = [0]*N
# enumerate関数は指定のリストにインデックス番号を振ることが可能
for i, num in enumerate(L):
    b[num-1] = i+1
# *はリストの個々の要素を取り出すことが可能
print(*b)
### BUGGY CODE ###

#! -*- coding:utf-8 -*-
n = int(input())
a = map(int,input().split())
a = list(a)
x = []
#a = []
#for i in range(200000):
#    a.append(i)

count = 0
for i in range(n):
    if count % 2 == 1:
        x.append(a[i])
    else:
        x.insert(0,a[i])

    count += 1

if n % 2 == 0:
    x.reverse()
    x = map(str,x)
    print(' '.join(x))

else:
    x = map(str,x)
    print(' '.join(x))


### FIXED CODE ###

n = int(input())
arr = input().split()
arr = list(map(int,arr))

b = [0] * n
center = n // 2
for i in range(n):
    if i % 2 == 0:
        b[center + (i//2)] = arr[i]
    else:
        b[center - ((i+1)//2)] = arr[i]

if n % 2 == 0:
    pass
else:
    b.reverse()

for i in range(n-1):
    print(b[i], end = ' ')
print(b[-1])
### BUGGY CODE ###

S = input()
N = int(input())
Q =[]
while True:
    try:
        Q.append(list(map(str,input().split())))
    except:
        break;
flag = True
for i in range(N):
    if Q[i][0]=="1":
        flag = not(flag)                
    else: 
        if (Q[i][1] == "2") == (flag == True):
            S += Q[i][2]#先頭
        else :
            S1 = Q[i][2]+ S
            S = S1

if flag == True:
    print(S)
else:
    print(S[::-1])  

### FIXED CODE ###

from sys import stdin
S = input()
x = S
y =str()   
N = int(input())
Q =  [list(map(str, stdin.readline().split())) for _ in range(N)]
flag = True
for i in range(N):
    if Q[i][0]=="1":
        flag = not(flag)                
    else: 
        if (Q[i][1] == "2") == (flag == True):
            x += Q[i][2]#先頭
        else :
            y += Q[i][2]
M = "".join([y[::-1],x])
if flag == True:
    print(M)
else:
    print(M[::-1])
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

# ある地点を渡すと、その地点から到達可能かつ距離未計算の地点のリストを返す
def not_investigated_positions(current_position):
    output = []
    for udrl in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        y = current_position[0]+udrl[0]
        x = current_position[1]+udrl[1]
        if 0 <= y <= H-1 and 0 <= x <= W-1:
            if S[y][x] == "." and distance[y][x] == -1:
                output.append([y, x])
    return output

ans = 0
for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if S[sy][sx] == "#" or S[gy][gx] == "#":
                    continue
                distance = [[-1]*W for _ in range(H)]
                current_position = [sy, sx]
                distance[sy][sx] = 0
                next_positions = deque()
                next_positions.append(current_position)

                while next_positions and current_position != [gy, gx]:
                    current_position = next_positions.popleft()
                    for q in not_investigated_positions(current_position):
                        distance[q[0]][q[1]] = distance[current_position[0]][current_position[1]] + 1
                        next_positions.append(q)

                ans = max(ans, distance[gy][gx])

print(ans)


### FIXED CODE ###

# D - Maze Master

from collections import deque

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

# ある地点を渡すと、その地点から到達可能かつ距離未計算の地点のリストを返す
def not_investigated_positions(current_position):
    output = []
    for udrl in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        y = current_position[0]+udrl[0]
        x = current_position[1]+udrl[1]
        if 0 <= y <= H-1 and 0 <= x <= W-1:
            if S[y][x] == "." and distance[y][x] == -1:
                output.append([y, x])
    return output

ans = 0

for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == "#":
            continue
        distance = [[-1]*W for _ in range(H)]
        current_position = [sy, sx]
        distance[sy][sx] = 0
        next_positions = deque()
        next_positions.append(current_position)

        while next_positions:
            current_position = next_positions.popleft()
            for q in not_investigated_positions(current_position):
                distance[q[0]][q[1]] = distance[current_position[0]][current_position[1]] + 1
                next_positions.append(q)

        ans = max(ans, max(map(max,distance)))

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

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

if a.count(1) == 0:
    print(-1)
else:
    i = 1
    idx = 0
    while idx < n:
        if i in a[idx:]:
            idx += a[idx:].index(i) + 1
            i += 1
        else:
            break

    print(n-i+1)

### FIXED CODE ###

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

if not 1 in a:
    print(-1)
else:
    cnt = 1
    for i in range(n):
        if a[i] == cnt:
            cnt += 1

    print(n - cnt + 1)