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

N = int(input())
C = input()
C = C.lstrip('R').rstrip('W')

ans = 0
for _ in range(10**5):
    if len(C) > 0:
        l = C.find('R')
        r = C[::-1].find('W')
        n = min(l, r)
        C = C[n:-n]
        C = C.lstrip('R').rstrip('W')
        ans += n
    else:
        break
print(ans)

### FIXED CODE ###

N = int(input())
C = input()

l, r = 0, N - 1
ans = 0
while l < r:
    if C[l] == 'R':
        l += 1
    elif C[r] == 'W':
        r -= 1
    else:
        ans += 1
        l += 1
        r -= 1
print(ans)
### BUGGY CODE ###

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

class value():
  def __init__(self, a, b):
    self.a = a
    self.b = b
  def __gt__(self, other):
    return self.a > other.a
  def __ge__(self, other):
    return self.a >= other.a

V = []
for i in range(N):
  a, b = [int(x) for x in input().split()]
  V.append(value(a, b))
  V.sort()

money = 0
i = 0

while True:
  v = V[i]
  if M <= v.b:
    break
  else:
    money += v.a * v.b
    M -= v.b
    i += 1
money += v.a * M
print(money)

### FIXED CODE ###

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

money = 0
count = 0

for a, b in V:
  if count + b < M:
    count += b
    money += a * b
  else:
    money += (M - count) * a
    break
print(money)
### BUGGY CODE ###

X = int(input())


def cal(x, c):
    if x == 0 or x % 100 == 0:
        print(1)
        exit()

    else:
        now = x - 100
        for i in range(1, 6):
            if now < i:
                return 0
            else:
                if c[i] > 19:
                    continue
                else:
                    cal(now-i, c[0:i:]+[c[i]+1]+c[i+1::])
    return 0


if X >= 2000:
    print(1)
else:
    print(cal(X, ([0 for _ in range(6)])))


### FIXED CODE ###

X = int(input())
for c in range(X//100 + 1):
    if 100*c <= X and X <= 105*c:
        print(1)
        exit()

print(0)
### BUGGY CODE ###

n = int(input())
c = str(input())
cn = [False]*n
for i in range(n):
    if c[i]=="R":
        cn[i]= True


ans = 0
k=n-1
b=0

for i in range(n):
    if b==1:
        break

    if cn[i]== False:
        for j in range(k,0,-1):

            if cn[j]==True:
                k =j-1
                if i < j:
                    cn[i]=True
                    #cn[j]=False
                    ans +=1
                    break
                elif i>=j:
                    b=1
                    break
print(ans)

### FIXED CODE ###

n = int(input())
c = str(input())
cn = [False]*n
for i in range(n):
    if c[i]=="R":
        cn[i]= True


ans = 0
k=n-1
b=0

for i in range(n):
    if b==1:
        break

    if not(cn[i]):
        for j in range(k,0,-1):

            if cn[j]:
                k =j-1
                if i < j:
                    #cn[i]=True
                    #cn[j]=False
                    ans +=1
                    break
            if i>=j:
                b=1
                break
print(ans)
### BUGGY CODE ###

S = str(input())
Q = int(input())
flip = 0
for i in range(Q):
  j = input()
  if len(j) == 1:
    flip += 1
    continue
  else:
    if j[2] == '1' and flip % 2 == 0:
      S = j[4] + S
      continue
    elif j[2] == '2' and flip % 2 == 0:
      S = S + j[4]
      continue
    elif j[2] == '1' and flip % 2 ==1:
      S = S + j[4]
      continue
    elif j[2] == '2' and flip % 2 ==1:
      S = j[4] + S
      continue
if flip % 2 == 1:
  S = S[::-1]
print(S)

### FIXED CODE ###

S = str(input())
Q = int(input())
flip = 0
front,back = '',''
for i in range(Q):
  j = input()
  if len(j) == 1:
    flip += 1
    continue
  else:
    if j[2] == '1' and flip % 2 == 0:
      front = j[4] + front
      continue
    elif j[2] == '2' and flip % 2 == 0:
      back = back + j[4]
      continue
    elif j[2] == '1' and flip % 2 ==1:
      back= back + j[4]
      continue
    elif j[2] == '2' and flip % 2 ==1:
      front = j[4] + front
      continue
S = front + S + back
if flip % 2 == 1:
  S = S[::-1]
print(S)
### BUGGY CODE ###

def main():
    def gcd(v1, v2):
        if v2 == 0:
            return v1
        return gcd(v2, v1%v2)

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a_lcm, a)

    res = 0
    for a in a_list:
        res = (res + a_lcm // a) % MOD
    print(res)

if __name__ == "__main__":
    main()


### FIXED CODE ###


from fractions import gcd
def main():

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a,a_lcm)

    res = 0
    for a in a_list:
        res += a_lcm // a
    print(res%MOD)

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

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush
import numpy as np


def small_dp(N,k,X):
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        return max(X[0][1]*i + X[1][1]*((N-i*X[0][0])//X[1][0]) + (N-i*X[0][0])%X[1][0] for i in range(N//X[0][0]+1))
    if k == 3:
        return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0])  for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    for C in ((A,B), (B,A)):
        *X, = filter(lambda c: int.__sub__(*c)<0, zip(*C))
        N = small_dp(N, len(X), X)
    res = N

    return str(res)

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


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

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

import sys

sys.setrecursionlimit(1000000000)

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

tree = [[] for _ in range(n)]
ope = [0]*n
ret=[0]*n

for i in range(n-1):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)

def counter(target,num):
    global ret
    global ope
    ret[target]+=num
    if not tree[target]:
        return
    for i in tree[target]:
        tmp=ope[i]
        counter(i,num+tmp)

for _ in range(q):
    p,x=map(int,input().split())
    ope[p-1]+=x

counter(0,ope[0])

print(*ret)

### FIXED CODE ###

n,q = map(int,input().split())
rl = [0] * n
al = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    rl[b-1] = a -1
for j in range(q):
    p,x = map(int,input().split())
    al[p-1] += x
for k in range(1,n):
    al[k] += al[rl[k]]
print(*al)
### BUGGY CODE ###

def main():
    N, D, A = map(int, input().split())

    XHN = []
    for _ in range(N):
        X, H = map(int, input().split())
        XHN.append([X, H, X + 2 * D])

    XHN.sort()

    q = []
    acc_damege = 0
    ans = 0
    for i in range(N):
        if 0 < XHN[i][1]:
            X, H, bomb_p = XHN[i]

            while q:
                acc_x, acc_d = q[0]
                if acc_x < X:
                    acc_damege -= acc_d
                    del q[0]
                else:
                    break

            H -= acc_damege

            if 0 < H:
                attack_count = H // -A * -1
                damege = A * attack_count
                ans += attack_count
                XHN[i][1] -= damege

                acc_damege += damege
                q.append((bomb_p, damege))

    print(ans)


main()


### FIXED CODE ###

from collections import deque


def main():
    N, D, A = map(int, input().split())

    XHN = []
    for _ in range(N):
        X, H = map(int, input().split())
        XHN.append([X, H, X + 2 * D])

    XHN.sort()

    q = deque()
    acc_damege = 0
    ans = 0
    for i in range(N):
        if 0 < XHN[i][1]:
            X, H, bomb_p = XHN[i]

            while q:
                acc_x, acc_d = q[0]
                if acc_x < X:
                    acc_damege -= acc_d
                    del q[0]
                else:
                    break

            H -= acc_damege

            if 0 < H:
                attack_count = H // -A * -1
                damege = A * attack_count
                ans += attack_count
                XHN[i][1] -= damege

                acc_damege += damege
                q.append((bomb_p, damege))

    print(ans)


main()
### BUGGY CODE ###

import sys
import numpy as np
 
input = sys.stdin.readline
 
N, K = map(int, input().split())
a = [int(i) for i in input().split()]

dp = [True for j in range(K+1)]
dp[0] = False

for j in range(K):
    for i in range(N):
        if j+1 - a[i] >= 0:
            dp[j+1] = dp[j+1] and dp[j+1 - a[i]]
    dp[j+1] = not dp[j+1]

if dp[-1]:
    print("First")
else:
    print("Second")

### FIXED CODE ###

import sys
 
input = sys.stdin.readline
 
N, K = map(int, input().rstrip("\n").split())
a = [int(i) for i in input().rstrip("\n").split()]

dp = [True for j in range(K+1)]
dp[0] = False

for j in range(K):
    for i in range(N):
        if j+1 - a[i] >= 0:
            dp[j+1] = dp[j+1] and dp[j+1 - a[i]]
    dp[j+1] = not dp[j+1]

if dp[-1]:
    print("First")
else:
    print("Second")
### BUGGY CODE ###

import bisect

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
L = [list(map(int,input().split())) for i in range(M)]
L = sorted(L, key=lambda x: x[1], reverse=True)

ans = 0

for i in range(M) :
    b,c = L[i]
    
    bi = bisect.bisect(A,c)
    
    K = min(b,bi)
    ans += c*K
    A = A[K:]
ans += sum(A)
print(ans)
    

### FIXED CODE ###

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

P = sorted(([[1,A[i]] for i in range(N)] + L),key=lambda x: x[1],reverse=True)

ans = 0
rest = N

for cost,value in P :
    K = min(cost, rest)
    K = max(0,K)
    ans += K * value
    rest -= cost

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

n, m = map(int, input().split())
group_num = [i + 1 for i in range(n)]
cnt = [0] * n

def find(x, y):
    if group_num[x - 1] == group_num[y - 1]:
        return True
    else:
        return False

def union(x, y):
    for i in range(n):
        if group_num[i] == group_num[x - 1]:
            group_num[i] = group_num[y - 1]
    return

for i in range(m):
    a, b = map(int, input().split())
    if find(a, b):
        continue
    else:
        union(a, b)

for i in range(n):
    cnt[group_num[i] - 1] += 1

print(max(cnt))

### FIXED CODE ###

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

par = [i + 1 for i in range(n)]
rank = [1] * n
size = [1] * n

def find(x):
    if par[x - 1] == x:
        return x
    else:
        return find(par[x - 1])

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x - 1] < rank[y - 1]:
        par[x - 1] = y
        size[y - 1] += size[x - 1]
    else:
        par[y - 1] = x
        size[x - 1] += size[y - 1]
        if rank[x - 1] == rank[y - 1]:
            rank[x - 1] += 1

for i in range(m):
    a, b = map(int, input().split())
    union(a, b)

print(max(size))
### BUGGY CODE ###

N, X, Y = map(int, input().split())
S = [list(reversed(list(range(1, i+1)))) + list(range(N-i)) for i in range(N)]

S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for i in range(N):
    for j in range(N):
        x, y = X-1, Y-1
        S[i][j] = min(S[i][j], S[i][x]+1+S[y][j])

#print(S)

dist = [0]*N

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

#print(dist)

for i in range(1, len(dist)):
    print(dist[i])


### FIXED CODE ###

N, X, Y = map(int, input().split())
S = [list(reversed(list(range(1, i+1)))) + list(range(N-i)) for i in range(N)]

S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for i in range(N):
    for j in range(N):
        x, y = X-1, Y-1
        S[i][j] = min(S[i][j], S[i][x]+1+S[y][j])

#print(S)

dist = [0]*N

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

#print(dist)

for i in range(1, len(dist)):
    print(dist[i])
### BUGGY CODE ###

N = input()
a = []
for i in range(N):
        a.append(input())
B = max(a)
for i in range(N):
        if a[i] != B:
                print(B)
        else:
                b = a.pop(i)
                print(max(a))
                a.insert(i,b)


### FIXED CODE ###

N = input()
a = []
for i in range(N):
        a.append(input())
b = sorted(a)
b0,b1 = b[-1],b[-2]
for i in range(N):
        if a[i]!=b0 :
                print(b0)
        else:
                print(b1)
### BUGGY CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
cmb = [0]*N
cmb[K-1] = 1
for i in range(K, N):
    cmb[i] = cmb[i-1]*i//(i - K + 1)

for i in range(N):
    fac = (cmb[i] - cmb[N-i-1])%(10**9+7)
    ans += fac*a[i]
    ans = ans%(10**9+7)
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mod = 10**9+7
ans = 0
cmb = [0]*N
x = [0]*N
cmb[K-1] = 1
def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod
for i in range(1,N-K+1):
    x[i] = Pow(i, mod-2)
    
for i in range(K, N):
    cmb[i] = cmb[i-1]*i%mod*x[i-K+1]%mod
for i in range(N):
    fac = cmb[i] - cmb[N-i-1]
    num = fac*a[i]%mod
    ans += num
    ans = ans%(10**9+7)
print(ans)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

    if s[-1]=='?':
        for i in range(10):
            dp[0][i] = 1
    else:
        a = int(s[-1])
        dp[0][a] = 1

    a = 1
    for i in range(1, n):
        a = 10 * a % 13
        if s[-(i+1)] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i][(a*j+k)%13] += dp[i-1][k] % mod
        else:
            j = int(s[-(i+1)])
            for k in range(13):
                dp[i][(a*j+k)%13] += dp[i-1][k] % mod
    print(dp[-1][5]%mod)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    dp = [[0]*13 for _ in range(n)]

    if s[-1]=='?':
        for i in range(10):
            dp[0][i] = 1
    else:
        a = int(s[-1])
        dp[0][a] = 1

    a = 1
    for i in range(1, n):
        a = 10 * a % 13
        if s[-(i+1)] == '?':
            for j in range(10):
                for k in range(13):
                    dp[i][(a*j+k)%13] += dp[i-1][k] % mod
        else:
            j = int(s[-(i+1)])
            for k in range(13):
                dp[i][(a*j+k)%13] += dp[i-1][k] % mod
    print(dp[-1][5]%mod)


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

N = int(input())
a = list(map(int, input().split()))
count = 0
if 1 not in a:
    print(-1)
else:
    count += a.index(1)
    prev_index = a.index(1)
    for i in range(prev_index):
        a[i] = 0
    for i in range(2,N+2):
        if i not in a:
            count += N - (prev_index + 1)
            print(count)
            break
        else:
            count += a.index(i) - prev_index -1
            two_ago_index = prev_index
            prev_index = a.index(i)
            for j in range(two_ago_index,prev_index+1):
                a[j] = 0

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
count = 1
brick = 0
for i in range(N):
    if a[i] != count:
        brick += 1
    else:
        count += 1
if brick == N:
    print(-1)
else:
    print(brick)
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, a, b = map(int, input().split())
MOD = 10**9+7
MAX = 2*10**5
fac = [0]*MAX
finv = [0]*MAX
inv = [0]*MAX


def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i-1]*i % MOD
        inv[i] = MOD-inv[MOD % i]*(MOD//i) % MOD
        finv[i] = finv[i-1]*inv[i] % MOD


def COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD


COMinit()

memo = defaultdict(int)


def RECOM(n, k):
    if memo[(n, k)] != 0:
        return memo[(n, k)]
    if MAX < n:
        return n*RECOM(n-1, k-1)//k
    else:
        memo[(n, k)] = COM(n, k)
        return memo[(n, k)]

ans = pow(2, n, MOD)-RECOM(n, a)-RECOM(n, b)-1
print(ans)

### FIXED CODE ###

n, a, b = map(int, input().split())
MOD = 10**9+7


def COM(n, r):
    X = Y = 1
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
    Y = pow(Y, MOD-2, MOD)
    while 0 < r:
        X = X*n % MOD
        n -= 1
        r -= 1
    return X*Y


ans = pow(2, n, MOD)-1 - COM(n, a)-COM(n, b)
ans %= MOD

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

import copy

n = int(input())
arr = [int(input()) for _ in range(n)]
ans = []

for ele in arr:
    tmp = copy.copy(arr)
    tmp.remove(ele)
    ans.append(max(tmp))

for ele in ans:
    print(ele)


### FIXED CODE ###

n = int(input())
arr = [int(input()) for _ in range(n)]
ar = sorted(arr)
mx = ar[-1]
sc = ar[-2]

for ele in arr:
    if ele == mx:
        print(sc)
    else:
        print(mx)
### BUGGY CODE ###

import math

N = int(input())
lis_all = []
lis_pat = []
lis_num = []

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

count = 0
for i in range(N):
    lis_S = list(str(input()))
    lis_S.sort()
    if lis_S not in lis_all:
        lis_pat.append(lis_S)
    lis_all.append(lis_S)

for i in lis_pat:
    lis_num.append(lis_all.count(i))

ans = 0
for i in lis_num:
    if i != 1:
        ans += comb(i,2)
   
print(ans)
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N=int(input())
dic={}
sum=0
for i in range(N):
    s=list(input())
    s.sort()
    s = "".join(s)
    if s in dic:
        sum+=dic[s]
        dic[s]+=1
    else:
        dic[s]=1
print(sum)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]
b = list(range(1, n+1))
for i in a:
  b.remove(i)

dp = [0] * (n+1)
dp[0] = 1

if b[0] == 1:
  dp[1] = 1
  b.pop(0)
else:
  dp[1] = 0

  
for i in b:
  dp[i] = (dp[i-1]%1000000007 + dp[i-2]%1000000007)%1000000007
  
print(dp[n]%1000000007)


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = [int(input()) for _ in range(m)]
a.append(0)

dp = [0] * (n+1)
dp[0] = 1
acounter = 0
if a[0] == 1:
  dp[1] = 0
  acounter = 1
else:
  dp[1] = 1

for i in range(2, n+1):
  if i == a[acounter]:
    dp[i]=0
    acounter+=1
  else:
    dp[i] = (dp[i-1]%1000000007 + dp[i-2]%1000000007)%1000000007
  
print(dp[n]%1000000007)
### BUGGY CODE ###

import copy
N = int(input())
K = [[1, N]]
for i in range(2, max(int(N**0.5)+1, 2)):
    if N % i == 0:
        K.append([i, N//i])

ans = 3*N
for i in range(len(K)):
    a, b = K[i]
    p = copy.copy(b)
    while(True):
        if b > ans:
            break
        if (2*b-1) % a == 0:
            ans = min(ans, 2*b-1)
        elif (2*b+1) % a == 0:
            ans = min(ans, 2*b)
        if b % 2 == 1:
            if ((b - 1) // 2) % a == 0:
                ans = min(ans, b - 1)
            elif ((b + 1) // 2) % a == 0:
                ans = min(ans, b)
        b += p

if N == 1:
    print(1)
elif N == 2:
    print(3)
else:
    print(ans)

### FIXED CODE ###

import math
def extgcd(a, b):
    """
    ax + by = gcd(a,b) = d となる (x,y,d) を返す
    """
    if b == 0:
        return (1, 0, a)
    q, r = a // b, a % b
    x, y, d = extgcd(b, r)
    s, t = y, x - q * y
    return s, t, d

def inv_mod(a, N):
    """
    ax = 1 mod N となる x を返す
    """
    return extgcd(a, N)[0]

def CRT(a_1, a_2, m_1, m_2):
    """
    x = a_1 mod m_1, x = a_2 mod m_2 となる x を返す
    """
    y = (a_2 - a_1) * inv_mod(m_1, m_2) % m_2
    return a_1 + m_1 * y

N = int(input())
N *= 2
K = [[1, N]]
for i in range(2, max(int(N**0.5)+1, 2)):
    if N % i == 0:
        K.append([i, N//i])

ans = float("inf")
for i in range(len(K)):
    a, b = K[i]
    if math.gcd(a, b) == 1:
        P = CRT(0, -1, a, b)
        if P != 0:
            ans = min(P, ans)
        Q = CRT(0, -1, b, a)
        if Q != 0:
            ans = min(Q, ans)

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

from itertools import product

n = int(input())
P = [0, 0] + [int(i) for i in input().split()]
X = [0] + [int(i) for i in input().split()]

C = [[] for i in range (n+1)]

for i, p in enumerate(P):
    C[p].append(i)

def dfs(i):
    if not C[i]:
        return X[i], 0
    A = []
    for c in C[i]:
        A.append(dfs(c))

    B = []
    for bits in range(2**(len(A)-1)):
        a, b = 0, 0
        for j, c in enumerate(A):
            a += c[bits >> j & 1]
            b += c[((bits >> j & 1) + 1) % 2]
        if a <= X[i]:
            B.append((X[i], b))
        if b <= X[i]:
            B.append((X[i], a))
    if not B:
        print('IMPOSSIBLE')
        exit()

    return min(B)

dfs(1)
print('POSSIBLE')

### FIXED CODE ###

from itertools import product

n = int(input())
P = [0, 0] + [int(i) for i in input().split()]
X = [0] + [int(i) for i in input().split()]

C = [[] for i in range (n+1)]

for i, p in enumerate(P):
    C[p].append(i)

def dfs(i):
    if not C[i]:
        return X[i], 0

    A = []
    
    for c in C[i]:
        A.append(dfs(c))

    S = 0
    for a in A:
        S += sum(a)

    dp = [[False]*(X[i]+1) for j in range(len(A)+1)]
    dp[0][0] = True

    for j in range(len(A)):
        for k in range(X[i]+1):
            a, b = A[j]
            if a <= k and dp[j][k-a]:
                dp[j+1][k] = True
            elif b <= k and dp[j][k-b]:
                dp[j+1][k] = True
        if not any(dp[j+1]):
            print('IMPOSSIBLE')
            exit()

    b = 0
    for j in range(X[i], -1, -1):
        if dp[len(A)][j]:
            b = j
            break

    return X[i], S - b

dfs(1)
print('POSSIBLE')