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

s_l = list(input())
result = [0] *len(s_l)

for i in range(len(s_l)):
    str_rl = s_l[i]
    shift = 0
    count = 0
    while str_rl == s_l[i]:
        if str_rl == 'R':
            shift += 1
        else:
            shift -= 1
        str_rl = s_l[i+shift]
        count += 1
    if count%2 != 0:
        if str_rl == 'R':
            shift += 1
        else:
            shift -= 1
    result[i+shift] += 1

print(' '.join(map(str,result)))

### FIXED CODE ###

s_l = list(input())
n = len(s_l)
result = [1] *len(s_l)

# only for R
for i in range(n):
    if s_l[i] == 'L':
        continue
    if s_l[i+1] == 'L':
        continue
    else:
        result[i+2] += result[i]
        result[i] = 0

# only for L
for i in range(n):
    j = n-1 - i
    if s_l[j] == 'R':
        continue
    if s_l[j-1] == 'R':
        continue
    else:
        result[j-2] += result[j]
        result[j] = 0

print(' '.join(map(str,result)))
### BUGGY CODE ###

import bisect
N = int(input())
 
c = []
for i in range(N):
    n = int(input())
    index = bisect.bisect_left(c,n)
    #print(index,c)
    if index == 0:
        c.insert(0,n)
    else:
        c[index-1] = n
    #print(c)
 
print(len(c)) 

### FIXED CODE ###

import bisect
N = int(input())

def bisect_right_reverse(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x > a[mid]: hi = mid
        else: lo = mid+1
    return hi


c = []
for i in range(N):
    n = int(input())
    index = bisect_right_reverse(c,n)
    #print(index)
    if index == len(c):
        c.append(n)
    else:
        c[index] = n
    #print(c)

print(len(c))
### BUGGY CODE ###

N = int(input())
lsn = list(map(int,input().split()))
Q = int(input())
ls2 = []
for i in range(Q):
    Bi,Ci = map(int,input().split())
    ls2.append([Bi,Ci])
index = [0]*(10**5+1)
for i in range(10**5+1):
    index[i] = lsn.count(i)
sum1 = sum(lsn)
for l in ls2:
    index[l[1]] += index[l[0]]
    sum1 = sum1 - l[0]*index[l[0]] + l[1]*index[l[0]]  
    index[l[0]] = 0
    print(sum1)

### FIXED CODE ###

import collections
N = int(input())
lsn = list(map(int,input().split()))
Q = int(input())
ls2 = []
for i in range(Q):
    Bi,Ci = map(int,input().split())
    ls2.append([Bi,Ci])
index = collections.Counter(lsn)
sum1 = sum(lsn)
for l in ls2:
    sum1 = sum1 +(l[1]-l[0])*index[l[0]]
    index[l[1]] += index[l[0]]
    index[l[0]] = 0
    print(sum1)
### BUGGY CODE ###

import itertools
n = int(input())
A = list(map(int, input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = abs(i-j)*A[i-1]
ans = 0
for x in itertools.permutations(range(1, n+1), n):
    cnt = 0
    for i, j in enumerate(x):
        cnt += dp[i+1][j]
    ans = max(ans, cnt)
print(ans)


### FIXED CODE ###

n = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()))]
A.sort(reverse=True)
dp = [[0]*(n+1) for _ in range(n+1)]
ans = 0
for L in range(n+1):
    for R in range(n+1):
        if n <= L+R-1:
            continue
        a, i = A[L+R-1]
        if 0 <= R-1:
            dp[L][R] = max(dp[L][R], dp[L][R-1]+abs((n-R)-i)*a)
        if 0 <= L-1:
            dp[L][R] = max(dp[L][R], dp[L-1][R]+abs(i-(L-1))*a)
        ans = max(ans, dp[L][R])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def f(N, x):
    n = 1
    for i in range(1, N):
        if i != x:
            n *= i
    return n


def main():
    N = int(input())
    X = list(map(int, input().split()))
    D = [0 for i in range(N)]

    for i in range(N-1):
        D[i] = X[i+1] - X[i]

    ans = 0
    r = 0
    mod = 10**9+7
    for i in range(1, N):
        r += f(N, i)
        r %= mod
        ans += D[i-1] * r
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline

mod = 10**9+7


def main():
    N = int(input())
    r1 = [1]
    for i in range(N-1):
        r1.append(r1[i] * (i+1) % mod)
    r2 = [1]
    for i in range(N-1):
        r2.append(r2[i] * (N-1-i) % mod)

    X = list(map(int, input().split()))
    D = [0 for i in range(N)]
    for i in range(N-1):
        D[i] = X[i+1] - X[i]

    ans = 0
    r = 0
    for i in range(N):
        r += r1[i] * r2[N-i-2]
        ans += D[i] * r
        ans %= mod
    print(ans)


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

n=int(input())
ans=0
l=sorted(list(map(int,input().split())))
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l[i]+l[j]>l[k]:
                ans+=1
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        x=bisect.bisect_left(l,l[i]+l[j])-j-1
        ans+=max(0,x)
print(ans)
### BUGGY CODE ###

# from collections import defaultdict
# dd = defaultdict(lambda: 0)

N = int(input())
T = [dict() for _ in range(N)]

for i in range(N-1):
    u, v, w = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    T[u][v] = w
    T[v][u] = w

opened = {0}
g0 = {0}
used = {0}

while len(opened) != 0:
    n = opened.pop()
    for n2 in T[n]:
        if n2 in g0:
            continue
        if n in g0:
            if T[n][n2] % 2 == 0:
                g0.add(n2)
        else:
            if T[n][n2] % 2 == 1:
                g0.add(n2)
        opened.add(n2)
        used.add(n2)

for i in range(N):
    print(0 if i in g0 else 1)






### FIXED CODE ###

# from collections import defaultdict
# dd = defaultdict(lambda: 0)

N = int(input())
T = [dict() for _ in range(N)]

for i in range(N-1):
    u, v, w = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    T[u][v] = w
    T[v][u] = w

opened = {0}
g0 = {0}
used = {0}

while len(opened) != 0:
    n = opened.pop()
    for n2 in T[n]:
        if n2 in used:
            continue
        if n in g0:
            if T[n][n2] % 2 == 0:
                g0.add(n2)
        else:
            if T[n][n2] % 2 == 1:
                g0.add(n2)
        opened.add(n2)
        used.add(n2)

for i in range(N):
    print(0 if i in g0 else 1)
### BUGGY CODE ###

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

cs = []
for i in range(m):
    b, c = map(int, input().split())
    cs += [c] * b

cards += cs
cards.sort(reverse = True)
    
print(sum(cards[:n]))

### FIXED CODE ###

n, m = map(int, input().split())
cards = [[1, int(i)] for i in input().split()]
bc = [list(map(int, input().split())) for _ in range(m)]
cards += bc
cards.sort(key = lambda x: x[1], reverse = True)

l = []
flag = 0
for i in cards:
    for j in range(i[0]):
        l.append(i[1])
        if len(l) == n:
            flag = 1
            break
    if flag:
        break

print(sum(l))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import copy

S = [ord(s) - ord('a') for s in input().rstrip()]

INF = 10 ** 9
N = len(S)
dp = [None] * (N+1)
# そこから始めたとき、次にxが現れる位置、および、次にxをとった場合に長さLのものが全て作れる
dp[N] = [[INF] * 26, [0] * 26, 0]

for n in range(N-1,-1,-1):
    prev = dp[n+1]
    cur = copy.deepcopy(prev)
    s = S[n]
    cur[0][s] = n
    cur[1][s] = prev[2] // 26 + 1
    cur[2] = prev[2] + cur[1][s] - prev[1][s]
    dp[n] = cur

answer = []
i = 0
while i < N:
    # 辞書順で、作れる長さが一番短い文字
    L = dp[i][2] // 26
    for x in range(26):
        if dp[i][1][x] == L:
            break
    answer.append(chr(ord('a') + x))
    # その文字の場所に移動
    i = dp[i][0][x]
    i += 1

print(''.join(answer))

### FIXED CODE ###

import sys
input = sys.stdin.readline

S = [ord(s) - ord('a') for s in input().rstrip()]

INF = 10 ** 9
N = len(S)
dp = [None] * (N+1)
# そこから始めたとき、次にxが現れる位置、および、次にxをとった場合に長さLのものが全て作れる
dp[N] = [[INF] * 26, [0] * 26, 0]

for n in range(N-1,-1,-1):
    prev = dp[n+1]
    cur = [prev[0].copy(), prev[1].copy(), prev[2]]
    s = S[n]
    cur[0][s] = n
    cur[1][s] = prev[2] // 26 + 1
    cur[2] = prev[2] + cur[1][s] - prev[1][s]
    dp[n] = cur

answer = []
i = 0
while i < N:
    # 辞書順で、作れる長さが一番短い文字
    L = dp[i][2] // 26
    for x in range(26):
        if dp[i][1][x] == L:
            break
    answer.append(chr(ord('a') + x))
    # その文字の場所に移動
    i = dp[i][0][x]
    i += 1

print(''.join(answer))
### BUGGY CODE ###

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

cnt = 0

for i in range(n):
    for j in range(n):
        if a[i] == a[j]:
            cnt += 1

if cnt == n:
    print("YES")
elif cnt > n:
    print("NO")

### FIXED CODE ###

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

if len(set(a)) == len(a):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

#coding utf-8

N,A,B=map(int,input().split())
data=[]
while len(data) < N:
  for r in range(A):
    data.append(1)
  for b in range(B):
    data.append(2)

list=data[0:N]
print(list.count(1))

### FIXED CODE ###

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

import math
import sys

n, a, b = [int(w) for w in input().split()]

ans = 0
while n > 0:
    if n >= a:
        n -= a
        ans += a
    else:
        ans += n
        n = 0
    n -= b

print(ans)


### FIXED CODE ###

import math
import sys

n, a, b = [int(w) for w in input().split()]

if a == 0:
    print(0)
    sys.exit()

if a + b >= n:
    print(min(a, n))
    sys.exit()

ans = 0
rep = n // (a + b)

ans += a * rep
n -= (a + b) * rep

ans += (min(a, n))

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

import numpy as np

def penetrate(x, y, idx):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1:
            d[nx][ny] = idx + 1


h, w = map(int, input().split())
d = [[-1] * w for _ in range(h)]

A = [[] for i in range(h)]

for i in range(h):
    A[i] = list(input())
    for j in range(w):
        if A[i][j] == "#":
            d[i][j] = 0

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

idx = 0
while True:
    count = 0
    for i in range(h):
        for j in range(w):
            if d[i][j] == idx:
                penetrate(i, j, idx)
            if d[i][j] == -1:
                count += 1
    idx += 1
    if count == 0:
        break

print(np.max(d))


### FIXED CODE ###

from collections import deque

def penetrate(x, y, count):
    global max_idx
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1:
            d[nx][ny] = count + 1
            q.append((nx, ny, d[nx][ny]))
            max_idx = max(max_idx, d[nx][ny])


h, w = map(int, input().split())
d = [[-1] * w for _ in range(h)]

A = [[] for i in range(h)]
q = deque()

for i in range(h):
    A[i] = list(input())
    for j in range(w):
        if A[i][j] == "#":
            d[i][j] = 0
            q.append((i, j, d[i][j]))

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

while len(q) > 0:
    idx = q.popleft()
    penetrate(idx[0], idx[1], idx[2])

print(max_idx)
### BUGGY CODE ###

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

cnt = 0
for i in range(1000):
  c = [i // 100, (i // 10) % 10, i % 10]
  f = 0
  for j in range(N):
    if S[j] == str(c[f]):
      f += 1
    if f == 3:
      break
  if f == 3:
    cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
for i in range(1000):
  c = str(i).zfill(3)
  if c[0] in S:
        index1 = S.index(c[0])
        if c[1] in S[index1+1:]:
            index2 = index1 + 1 + S[index1+1:].index(c[1])
            if c[2] in S[index2+1:]:
                cnt+=1
print(cnt)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())
L = []
R = []
for q in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

for q in range(Q):
    S_temp = S[L[q]-1:R[q]]
    count = S_temp.count('AC')
    print(count)


### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
W = [0] * (N+1)
L = []
R = []
for q in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

for n in range(N-1):
    W[n+1] = W[n] + (1 if S[n:n+2] == 'AC' else 0)    

for q in range(Q):
    print(W[R[q]-1]-W[L[q]-1])
### BUGGY CODE ###


import sys
input = sys.stdin.readline
def main():
  n,q=map(int,input().split())
  c=list(map(int,input().split()))
  lr=[list(map(int,input().split())) for _ in range(q)]
  lri=[[lr[i][0],lr[i][1],i] for i in range(q)]
  lri.sort(key=lambda x:x[1])
  
  class BIT:
      def __init__(self, n):
          self.n = n
          self.data = [0]*(n+1)
          self.el = [0]*(n+1)
      def sum(self, i):
          s = 0
          while i > 0:
              s += self.data[i]
              i -= i & -i
          return s
      def add(self, i, x):
          # assert i > 0
          self.el[i] += x
          while i <= self.n:
              self.data[i] += x
              i += i & -i
      def get(self, i, j=None):
          if j is None:
              return self.el[i]
          return self.sum(j) - self.sum(i)

  bt=BIT(n+1)
  dc={}
  ans=[0]*q
  j=0
  for i in range(n):
    x=c[i]
    if x in dc:
      bt.add(dc[x],-1)
    bt.add(i+1,1)
    dc[x]=i+1
    while j<q and i+1==lri[j][1]:
      l,r,k=lri[j]
      ans[k]=bt.get(l-1,r)
      j+=1
    if j==q:break
  print(*ans,sep='\n')


if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())


### FIXED CODE ###


import sys
input = sys.stdin.readline
def main():
  n,q=map(int,input().split())
  c=list(map(int,input().split()))
  lr=[list(map(int,input().split())) for _ in range(q)]
  lri=[[lr[i][0],lr[i][1],i] for i in range(q)]
  lri.sort(key=lambda x:x[1])
  
  class BIT:
      def __init__(self, n):
          self.n = n
          self.data = [0]*(n+1)
          self.el = [0]*(n+1)
      def sum(self, i):
          s = 0
          while i > 0:
              s += self.data[i]
              i -= i & -i
          return s
      def add(self, i, x):
          # assert i > 0
          self.el[i] += x
          while i <= self.n:
              self.data[i] += x
              i += i & -i
      def get(self, i, j=None):
          if j is None:
              return self.el[i]
          return self.sum(j) - self.sum(i)

  bt=BIT(n+1)
  dc={}
  ans=[0]*q
  j=0
  for i in range(n):
    x=c[i]
    if x in dc:
      bt.add(dc[x],-1)
    bt.add(i+1,1)
    dc[x]=i+1
    while j<q and i+1==lri[j][1]:
      l,r,k=lri[j]
      ans[k]=bt.get(l-1,r)
      j+=1
    if j==q:break
  print(*ans,sep='\n')


if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())
### BUGGY CODE ###

import sys

input = sys.stdin.buffer.readline

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

max_n = 300000
num = 1 << ((max_n - 1).bit_length())
SEG = [0] * (2 * num)

func = max
ele = 0


def update(idx, val):
    idx += num
    SEG[idx] = val
    for i in reversed(range(1, num)):
        SEG[i] = func(SEG[2 * i], SEG[2 * i + 1])


def query(left, right):
    res_left = ele
    res_right = ele
    left += num
    right += num
    while left < right:
        if left & 1:
            res_left = func(res_left, SEG[left])
            left += 1
        if right & 1:
            right -= 1
            res_right = func(SEG[right], res_right)
        left //= 2
        right //= 2
    return func(res_left, res_right)


for _ in range(n):
    val = int(input())
    # print("range", max(0, val - k), min(max_n + 1, val + k + 1) - 1)
    temp = query(max(0, val - k), min(max_n + 1, val + k + 1))
    # print(temp)
    temp += 1
    update(val, temp)
    # print(val, temp)
    # print(SEG[num : num + 12])

print(SEG[1])



### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline


class SegmentTree:
    ele = 0
    func = max
    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    # 1点更新
    def set(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    # 区間取得
    def query(self, left, right):
        # 開区間
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


n, k = map(int, input().split())
ans = 0
ST = SegmentTree(3000001)
for _ in range(n):
    val = int(input())
    lower = val - k
    lower = max(lower, 0)
    upper = val + k
    upper = min(upper, 3000000)
    temp = ST.query(lower, upper + 1) + 1
    ST.set(val, temp)
    ans = max(ans, temp)
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
for i in range(K):
    if not H: continue
    max_val = max(H)
    H.pop(H.index(max_val))
print(sum(H))

### FIXED CODE ###

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

sort_H = sorted(H)
if N >= K:
    print(sum(sort_H[0:N-K]))
else:
    print('0')
### BUGGY CODE ###

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in px:
    value[p] += x

from collections import deque
todo = deque([[1,0]])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append([y,x])

print(*value[1:])

### FIXED CODE ###

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in px:
    value[p] += x

from collections import deque
todo = deque([(1,0)])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

N = int(input())
a = 0
while N != 0:
    a += N%10
    N //= 10
if a % 9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = int(input())
if N % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N = int(input())
S = input()
num = 10**9+7
count = 0
for i in range(N):
  tmp = S[i]
  list_ = [tmp]
  for j in range(i+1,N):
    if S[j] != tmp:
      for k in range(len(list_)):
        if S[j] not in list_[k]:
          list_.append(list_[k]+S[j])
  count+=len(list_)
print(count%num)


### FIXED CODE ###

N = int(input())
S = list(input())
num = 10**9+7
ans = 1
s = set(S)
for i in s:
  ans *= S.count(i)+1
print(ans%num-1)
### BUGGY CODE ###

N = int(input())

A = [int(x) for x in input().split()]

for j in range(N):
    b = A.count(j+1)
    print(b)
    if b != 0:
        A.remove(j+1)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [0] * N
for i in range(N-1):
    B[(A[i]-1)] += 1

for j in range(N):
    print(B[j])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import permutations, product
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = [[inf for _ in range(N+1)] for _ in range(N+1)]
D = inpl() # destination

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

for n in range(N+1):
    G[n][n] = 0

for i ,j, k in product(range(1, N+1), repeat=3):
    G[j][k] = min(G[j][k], G[j][i] + G[i][k])

res = inf
for C in permutations(D, len(D)):
    res = min(res, sum([G[C[i]][C[i+1]] for i in range(len(D)-1)]))

print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import permutations, product
def inpl(): return tuple(map(int, input().split()))
N, M, R = inpl()
inf = float("inf")
G = [[inf for _ in range(N+1)] for _ in range(N+1)]
D = inpl() # destination

for _ in range(M):
    a, b, c = inpl()
    G[a][b] = c
    G[b][a] = c

for n in range(N+1):
    G[n][n] = 0

for i ,j, k in product(range(1, N+1), repeat=3):
    G[j][k] = min(G[j][k], G[j][i] + G[i][k])

res = inf
for C in permutations(D, len(D)):
    res = min(res, sum([G[C[i]][C[i+1]] for i in range(len(D)-1)]))

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

import itertools
from functools import reduce
from operator import mul


def trial_division(n):
  factors = []
  f = 2
  while f**2 <= n:
    if n % f == 0:
      n //= f
      factors.append(f)
    else:
      f += 1
  if n != 1:
    factors.append(n)
  return factors

N = int(input())
factors = trial_division(N)

if len(factors) == 1:
  print(factors[0]-1)
else:
  res = N
  cumsum = reduce(mul, factors)
  for i in range(len(factors)//2):
    for comb in itertools.combinations(factors, i+1):
      a = reduce(mul, comb)
      b = cumsum // a
      if a+b-2 < res:
        res = a+b-2
  print(res)


### FIXED CODE ###

N = int(input())

ans = N**2
for i in range(1, int(N**(1/2))+1):
  if N % i == 0:
    j = N // i
    ans = min(ans, (i-1)+(j-1))

print(ans)