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

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    X = il()

    ret = MAX
    for n in range(N - K + 1):
        C = X[n:n + K]
        ret = min(ret, abs(X[n]) + abs(X[n] - X[n+K-1]), abs(X[n+K-1]) + abs(X[n] - X[n+K-1]))
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    X = il()

    ret = MAX
    for n in range(N - K + 1):
        l = abs(X[n]) + abs(X[n]-X[n+K-1])
        r = abs(X[n+K-1]) + abs(X[n+K-1] - X[n])
        ret = min(ret, l, r)
    print(ret)


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

import math


def combinations_count(n, r):
    return (n*(n-1)//2)
    # return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

cnt = 0
ansx = []
ansy = []


for i in Ay:
    for j in Ay:
        if i == j and A.count(j) >= 3:
            cnt += combinations_count(A.count(j)-1, 2)
        elif i != j and A.count(j) >= 2:
            cnt += combinations_count(A.count(j), 2)
    ansx.append(i)
    ansy.append(cnt)
    cnt = 0

for i in A:
    print(ansy[ansx.index(i)])


### FIXED CODE ###

import collections
import math

N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
cnt = 0


sumall = 0
for x, y in c.items():
    sumall += (y*(y-1)//2)

for i in range(N):
    print(sumall - c[A[i]] + 1)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
a=[]
for i in range(n):
    if p[i] == min (p[:i+1]):
        a.append(p[i])
print(len(a))

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
ans=0
m=[]
m.append(p[0])
for i in range(1,n):
    m.append(min(p[i],m[i-1]))

for i , j in zip(p,m):
    if i <= j:
        ans+=1
print(ans)
### BUGGY CODE ###

import heapq
n,m,s,t = map(int,input().split())
edgeY = [[] for _ in range(n)]
edgeS = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    edgeY[u-1].append([a, v-1])
    edgeY[v-1].append([a, u-1])
    edgeS[u-1].append([b, v-1])
    edgeS[v-1].append([b, u-1])
costY = [float('inf')]*n
costS = [float('inf')]*n
costY[s-1] = 0
costS[t-1] = 0

# 円の時
q = []
for i in edgeY[s-1]:
    heapq.heappush(q, i)
while len(q):
    nowEdge = heapq.heappop(q)
    if costY[nowEdge[1]] == float('inf'):
        costY[nowEdge[1]] = nowEdge[0]
        for i in edgeY[nowEdge[1]]:
            heapq.heappush(q , [i[0]+costY[nowEdge[1]], i[1]])

# スヌークの時
q = []
for i in edgeS[t-1]:
    heapq.heappush(q, i)        
while len(q):
    nowEdge = heapq.heappop(q)
    if costS[nowEdge[1]] == float('inf'):
        costS[nowEdge[1]] = nowEdge[0]
        for i in edgeS[nowEdge[1]]:
            heapq.heappush(q , [i[0]+costS[nowEdge[1]], i[1]])
cost = []
ans = []
first = 10**15
minCost = 10**15
for i in range(n-1,-1,-1):
    nowCost = costY[i]+costS[i]
    if minCost > nowCost:
        minCost = nowCost
    ans.append(minCost)
for i in range(n-1,-1,-1):
    print(first- ans[i])

### FIXED CODE ###

import heapq
n,m,s,t = map(int,input().split())
edgeY = [[] for _ in range(n)]
edgeS = [[] for _ in range(n)]
for i in range(m):
    u,v,a,b = map(int,input().split())
    edgeY[u-1].append((a, v-1))
    edgeY[v-1].append((a, u-1))
    edgeS[u-1].append((b, v-1))
    edgeS[v-1].append((b, u-1))
costY = [float('inf')]*n
costS = [float('inf')]*n
costY[s-1] = 0
costS[t-1] = 0

# 円の時
q = []
for i in edgeY[s-1]:
    heapq.heappush(q, i)
while len(q):
    nowEdge = heapq.heappop(q)
    if costY[nowEdge[1]] == float('inf'):
        costY[nowEdge[1]] = nowEdge[0]
        for i in edgeY[nowEdge[1]]:
            heapq.heappush(q , (i[0]+costY[nowEdge[1]], i[1]))

# スヌークの時
q = []
for i in edgeS[t-1]:
    heapq.heappush(q, i)        
while len(q):
    nowEdge = heapq.heappop(q)
    if costS[nowEdge[1]] == float('inf'):
        costS[nowEdge[1]] = nowEdge[0]
        for i in edgeS[nowEdge[1]]:
            heapq.heappush(q , (i[0]+costS[nowEdge[1]], i[1]))
cost = []
ans = []
first = 10**15
minCost = 10**15
for i in range(n-1,-1,-1):
    nowCost = costY[i]+costS[i]
    if minCost > nowCost:
        minCost = nowCost
    ans.append(minCost)
for i in range(n-1,-1,-1):
    print(first- ans[i])
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for ri in range(N//R+1):
  if ri*R > N: continue
  for gi in range(N//G+1):
    if gi*G > N: continue
    for bi in range(N//B+1):
      if bi*B > N: continue
      if ri*R+gi*G+bi*B==N:ans += 1
print(ans)

### FIXED CODE ###

R,G,B,N = map(int,input().split())
ans = 0
for ri in range(N//R+1):
  for gi in range(N//G+1):
    if (N-ri*R-gi*G)>=0 and (N-ri*R-gi*G)%B==0:ans += 1
print(ans)
### BUGGY CODE ###

Q = int(input())
isPrime = [True] * 100001
for p in range(2, 100001):
    if isPrime[p]:
       for i in range(p * p, 100001, p):
           isPrime[i] = False
           
isPrime[1],isPrime[2] = False,True
for i in range(Q):
    ans = 0
    l,r = map(int,input().split())
    for c in range(l,r+1,2):
        other = (c+1)//2
        if isPrime[c] == -1:
            for j in range(2,int(c**0.5)+1):
                if c % j == 0:
                    isPrime[c] = False
                    break
            else:
                isPrime[c] = True
        if isPrime[other] == -1:
            for j in range(2,int(other**0.5)+1):
                if other % j == 0:
                    isPrime[other] = False
                    break
            else:
                isPrime[other] = True
                
        if isPrime[c] and isPrime[other]:
            ans += 1
    print(ans)
    


### FIXED CODE ###

Q = int(input())
isPrime = [True] * 100001
for p in range(2, 100001):
    if isPrime[p]:
       for i in range(p * p, 100001, p):
           isPrime[i] = False
isPrime[1],isPrime[2] = False,True

like_2017 = [0] * 100002
for i in range(1,100001):
    if isPrime[i] and isPrime[(i+1)//2]:
        like_2017[i] = like_2017[i-1] + 1
    else:
        like_2017[i] = like_2017[i-1]
        
for i in range(Q):
    l,r = map(int,input().split())
    print(like_2017[r] - like_2017[l-1])
### BUGGY CODE ###

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

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    col1 = np.concatenate([['*'],col1])
    col2 = np.concatenate([['#'],col2])
    equal = (col1[:,None] == col2[None,:])
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    L = np.arange(H+1)
    R = np.arange(H+1)
    dp_1[R[None,:]-L[:,None]+H,R[None,:]+L[:,None]] = equal
    np.cumsum(dp_1,out=dp_1,axis=1)
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)

### FIXED CODE ###

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

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, M, V, P = map(int, input().split())
A_list = list(map(int, input().split()))

A_list.sort(reverse = True)
# print(A_list)
ans = P
border = A_list[P - 1]

if P < N:
    before_A = border
    for i in range(P, N):
        if before_A == A_list[i]:
            ans += 1
#             print(1, i, A_list[i])
        elif border <= (A_list[i] + M):
            over_V = V - (P + N - (i + 1))
            if over_V > 0:
                sum_over = sum(A_list[P - 1:i]) + over_V * M
                round_up_sum_over = -(-sum_over // (i + 1 - P))
                if A_list[i] + M >= round_up_sum_over:
                    ans += 1
#                     print(2, i, A_list[i], round_up_sum_over, over_V, sum_over)
                else:
#                     print("NG", i, A_list[i], round_up_sum_over, over_V)
                    break
            else:
                ans += 1
#                 print(3, i, A_list[i])
            before_A = A_list[i]
        else:
            break
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, M, V, P = map(int, input().split())
A_list = list(map(int, input().split()))

A_list.sort(reverse = True)
# print(A_list)
ans = P
border = A_list[P - 1]
sum_over_A = border

if P < N:
    before_A = border
    for i in range(P, N):
        if before_A == A_list[i]:
            ans += 1
#             print(1, i, A_list[i])
        elif border <= (A_list[i] + M):
            over_V = V - (P + N - (i + 1))
            if over_V > 0:
                sum_over = sum_over_A + over_V * M
                round_up_sum_over = -(-sum_over // (i + 1 - P))
                if A_list[i] + M >= round_up_sum_over:
                    ans += 1
#                     print(2, i, A_list[i], round_up_sum_over, over_V, sum_over)
                else:
#                     print("NG", i, A_list[i], round_up_sum_over, over_V)
                    break
            else:
                ans += 1
#                 print(3, i, A_list[i])
            before_A = A_list[i]
        else:
            break
        sum_over_A += A_list[i]
print(ans)
### BUGGY CODE ###

import sys
import math
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X[:-1]] #最後までの距離
Y = [(limit // i)%MOD for i in range(1, N)]
answer = 0
for x, y in zip(X, Y):
    answer += (x*y)%MOD
    answer %= MOD

print(answer)


### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

MOD = 10 ** 9 + 7
U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
N = ir()
X = np.array(lr())

inv = np.zeros(U, np.int64)
inv[1:] = fact_inv[1:] * fact[:-1] % MOD
coef = inv[1:N].cumsum() % MOD
answer = (np.diff(X) * coef % MOD).sum() % MOD
answer *= fact[N-1]
print(answer % MOD)
# 35
### BUGGY CODE ###

def digits_parade(S: str)->int:
    MOD = 10**9 + 7
    DIV = 13
    # dp[i][j] = S の i 桁目までを利用してできる整数で 13 で割ったあまりが j になる組み合わせ
    dp = [[0] * DIV for _ in range(len(S)+1)]
    dp[0][0] = 1

    # digit: 10^n % 13 を計算するための変数
    digit = 1

    for i, c in enumerate(reversed(S)):
        if c == '?':
            for n in range(10):
                d = (n * digit) % DIV
                for j in range(DIV):
                    dp[i+1][(j+d) % DIV] += dp[i][j]
                    dp[i+1][(j+d) % DIV] %= MOD
        else:
            d = (int(c) * digit) % DIV
            for j in range(DIV):
                dp[i+1][(j+d) % DIV] += dp[i][j]
                dp[i+1][(j+d) % DIV] %= MOD

        digit = (digit * 10) % DIV

    return dp[len(S)][5]


if __name__ == "__main__":
    S = input()
    ans = digits_parade(S)
    print(ans)


### FIXED CODE ###

def digits_parade(S: str)->int:
    MOD = 10**9 + 7
    DIV = 13
    # dp[i][j] = S の i 桁目までを利用してできる整数で 13 で割ったあまりが j になる組み合わせ
    dp = [[0] * DIV for _ in range(len(S)+1)]
    dp[0][0] = 1

    # digit: 10^n % 13 を計算するための変数
    digit = 1

    for i, c in enumerate(reversed(S)):
        if c == '?':
            for n in range(10):
                d = (n * digit) % DIV
                for j in range(DIV):
                    dp[i+1][(j+d) % DIV] += dp[i][j]
                    dp[i+1][(j+d) % DIV] %= MOD
        else:
            d = (int(c) * digit) % DIV
            for j in range(DIV):
                dp[i+1][(j+d) % DIV] += dp[i][j]
                dp[i+1][(j+d) % DIV] %= MOD

        digit = (digit * 10) % DIV

    return dp[len(S)][5]


if __name__ == "__main__":
    S = input()
    ans = digits_parade(S)
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from itertools import combinations


def solve(N, A):
    # bg = []
    # sm = []
    cl = set()
    for i in range(N):
        if A[i] <= i - 1:
            # bg.append(i)
            cl.add(i)
        if A[i] >= 1 - i:
            # sm.append(i)
            cl.add(i)
    L = list(combinations(cl, 2))
    ct = 0
    for l in L:
        if abs(l[0] - l[1]) == A[l[0]] + A[l[1]]:
            ct += 1
    print(ct)
    # L = list(combinations(range(N), 2))
    # ct = 0
    # for l in L:
    #     if abs(l[0] - l[1]) == A[l[0]] + A[l[1]]:
    #         ct += 1
    # print(ct)
    return

# Generated by 1.1.6 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()
    N = int(next(tokens))
    A = [int(next(tokens)) for _ in range(N)]
    solve(N, A)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import product
from collections import Counter
# from itertools import combinations


def solve(N, A):
    B = [i - A[i] for i in range(N)]
    C = [i + A[i] for i in range(N)]
    Bc = Counter(B)
    Cc = Counter(C)
    ct = 0
    for k, i in Bc.items():
        if k in Cc:
            ct += i * Cc[k]
    print(ct)
    # bg = []
    # sm = []
    # # cl = set()
    # for i in range(N):
    #     if A[i] <= i - 1:
    #         bg.append(i)
    #         # cl.add(i)
    #     if A[i] >= 1 - i:
    #         sm.append(i)
    #         # cl.add(i)
    # # L = list(combinations(cl, 2))
    # L = list(product(bg, sm))
    # ct = 0
    # for l in L:
    #     if l[0] > l[1]:
    #         if abs(l[0] - l[1]) == A[l[0]] + A[l[1]]:
    #             ct += 1
    # print(ct)
    # # L = list(combinations(range(N), 2))
    # # ct = 0
    # # for l in L:
    # #     if abs(l[0] - l[1]) == A[l[0]] + A[l[1]]:
    # #         ct += 1
    # # print(ct)
    # return

# Generated by 1.1.6 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()
    N = int(next(tokens))
    A = [int(next(tokens)) for _ in range(N)]
    solve(N, A)

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

N = int(input())
A = list(map(int, input().split()))
gcd_list=[]
reverse_gcd_list = []
num = 0
gcd_num = 0

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

gcd_list.append(A[0])
for i in range(1,N):
    gcd_list.append(gcd(gcd_list[i-1], A[i]))

reverse_gcd_list.append(A[-1])
for i in range(1,N):
    reverse_gcd_list.insert(0,gcd(reverse_gcd_list[0], A[-1-i]))

for i in range(N-2):
    num = max(gcd(gcd_list[i], reverse_gcd_list[i+2]), num)

print(max(num, gcd_list[-2], reverse_gcd_list[1]))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
gcd_list=[]
reverse_gcd_list = []


def gcd(x,y):
    if x<y:
        x,y=y,x
    #x>y
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)

gcd_list.append(A[0])
reverse_gcd_list.append(A[-1])

for i in range(1,N):
    gcd_list.append(gcd(gcd_list[i-1], A[i]))
    # reverse_gcd_list.insert(0,gcd(reverse_gcd_list[0], A[-1-i]))
    reverse_gcd_list.append(gcd(reverse_gcd_list[-1], A[-1-i]))

reverse_gcd_list.reverse()
num = [gcd_list[-2], reverse_gcd_list[1]]
for i in range(N-2):
    num.append(gcd(gcd_list[i], reverse_gcd_list[i+2]))

print(max(num))
### BUGGY CODE ###

import sys

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

INF = 1e9
MAX = max(x[0] for x in MAGICS)
DP = [INF for _ in range(H+1)]

DP[0] = 0

for h in range(H+1):
    for magic  in MAGICS:
        DP[h] = min(DP[max(h - magic[0], 0)] + magic[1], DP[h])

print(DP[H])

### FIXED CODE ###

import sys

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

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])
### BUGGY CODE ###


if __name__ == '__main__':
    n, k = list(map(int, input().split(" ")))
    p = list(map(int, input().split(" ")))

    max_sum = 0
    rangeN = n - k + 1
    # for i in range(rangeN):
    #     # print(i, p, k)
    #     r = sum(p[i:i + k])
    #     # print(r)
    #     if r > max_sum:
    #         max_sum = r

    r_array = [sum(p[i:i + k]) for i in range(rangeN)]
    print((max(r_array) / 2) + (k * 0.5))

### FIXED CODE ###

from collections import deque

if __name__ == '__main__':
    n, k = list(map(int, input().split(" ")))
    p = list(map(int, input().split(" ")))

    d = deque([0])
    for i in range(n):
        d.append(d[i] + p[i])

    # print(d)

    max_sum = 0
    rangeN = n - k + 1

    for i in range(rangeN):
        max_sum = max(max_sum, d[i + k] - d[i])
    # print(max_sum)

    # r_array = [sum(p[i:i + k]) for i in range(rangeN)]
    print((max_sum / 2) + (k * 0.5))
### BUGGY CODE ###

n=int(input())
p=input().split()
flag=2*10**5+1
ans=0
for i in range(1,(n+1)):
    idx=p.index(str(i))
    if flag>idx:
        ans+=1
        flag=idx
print(ans)


### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
flag=2*10**5+1
ans=0
for i in range(n):
    if flag>int(p[i]):
        ans+=1
    flag=min(flag,p[i])
print(ans)
### BUGGY CODE ###

import itertools
from math import factorial
N = int(input())
L = tuple(map(int, input().split()))
nums = [0] * (N-3) + [1, 1, 1]
ans = 0
for ptr in itertools.permutations(nums):
    edge = []
    for i, v in enumerate(ptr):
        if v == 1:
            edge.append(L[i])
    if edge[0] < edge[1] + edge[2] and edge[1] < edge[2] + edge[0] and edge[2] < edge[0] + edge[1]:
        ans += 1
ans //= (factorial(3)*factorial(N-3))
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
ans = 0
L.sort()
for a_i in range(N-2):
    for b_j in range(a_i+1, N-1):
        c_idx = bisect.bisect_left(L, L[a_i]+L[b_j])
        if c_idx > b_j:
            ans += c_idx - b_j - 1
print(ans)
### BUGGY CODE ###

n,q = [int(x) for x in input().split()]
s = input()
lst = []
for _ in range(q):
    l,r = [int(x) for x in input().split()]
    lst.append([l,r])

c_lst = [x for x in range(n) if s[x] == "C" and s[x-1] == "A"]

cnt = 0
for i in range(q):
    for x in c_lst:
        if x+1 <= lst[i][0]:
            pass
        elif x+1 <= lst[i][1]:
            cnt += 1
        else:
            break
    print(cnt)
    cnt = 0


### FIXED CODE ###

n,q = [int(x) for x in input().split()]
s = input()

t = [0]*(n+1)
for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == "AC" else 0)

for _ in range(q):
    l,r = [int(x) for x in input().split()]
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

S = input()
Q = int(input())
count = 0
right = ''
left = ''
for i in range(Q):
    arr = list(input().split())
    if len(arr) == 1:
        count += 1
    else:
        if arr[1] == '1':
            if count%2==0:
                S = arr[2] + S
            else:
                S = S + arr[2]
        else:
            if count%2!=0:
                S = arr[2] + S
            else:
                S = S + arr[2]
if count%2 == 0:
    print(S)
else:
    ans = ''
    for i in S:
        ans = i + ans
    print(ans)

### FIXED CODE ###

S = input()
Q = int(input())
count = 0
right = ''
left = ''
for i in range(Q):
    arr = list(input().split())
    if len(arr) == 1:
        count += 1
    else:
        if arr[1] == '1':
            if count%2==0:
                left = arr[2] + left
            else:
                right = right + arr[2]
        else:
            if count%2!=0:
                left = arr[2] + left
            else:
                right = right + arr[2]
S = left + S + right
if count%2 == 0:
    print(S)
else:
    print(S[::-1])