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

s = input()
t = input()
q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    cnts = cntt = 0
    for i in range(a-1, b):
        cnts += 1 if s[i] == 'A' else 2
    for i in range(c-1, d):
        cntt += 1 if t[i] == 'A' else 2
    print("YES" if cnts%3 == cntt%3 else "NO")

### FIXED CODE ###

s = input()
t = input()
ssum = [0 for _ in range(len(s)+1)]
for i in range(len(s)):
    ssum[i+1] = ssum[i] + (s[i] == 'A')
tsum = [0 for _ in range(len(t)+1)]
for i in range(len(t)):
    tsum[i+1] = tsum[i] + (t[i] == 'A')
q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    cnts = (b-a+1)*2 - (ssum[b] - ssum[a-1])
    cntt = (d-c+1)*2 - (tsum[d] - tsum[c-1])
    print("YES" if cnts % 3 == cntt % 3 else "NO")
### BUGGY CODE ###

n = int(input())
s = input()
d = {'R':0,'G':0,'B':0}
for i in s:
    d[i] += 1
c = d['R'] * d['G'] * d['B']

for i in range(n):
    for j in range(i+1,n):
        k = 2 * j - i
        if(k <= j or k >= n):continue
        if(s[i] == s[j]):continue
        if(s[j] == s[k]):continue
        if(s[i] == s[k]):continue
        c -= 1

print(c)

### FIXED CODE ###

n = int(input())
s = input()
d = [0,0,0]
for i in s:
    if(i == 'R'):d[0] += 1
    elif(i == 'G'):d[1] += 1
    elif(i == 'B'):d[2] += 1
c = d[0] * d[1] * d[2]

for i in range(n):
    for j in range(i+1,n):
        k = 2 * j - i
        if(k >= n):continue
        if(s[i] == s[j]):continue
        if(s[j] == s[k]):continue
        if(s[i] == s[k]):continue
        c -= 1

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

# input here
_INPUT = """\
4
141421356 17320508 22360679 244949
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    n = int(input())
    a = list(map(int, input().split()))

    sum1 = 0
    for i in range(len(a)):
        mult = a[i] * sum(a[i+1:])
        sum1 += mult

    print((sum1 % (10**9 + 7)))


if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

### FIXED CODE ###

# input here
_INPUT = """\
4
141421356 17320508 22360679 244949
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    n = int(input())
    a = list(map(int, input().split()))
    cumsum = list(itertools.accumulate(a))

    sum1 = 0
    for i in range(len(a)):
        mult = a[i] * (cumsum[n-1] - cumsum[i])
        sum1 += mult

    print((sum1 % (10**9 + 7)))


if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()
### BUGGY CODE ###

#coding: utf-8
a = input()

b = []
n = 0
J = 0
flag = True
for i in range(len(a)):
    b.append(a[i])
c = b

while(flag):
    for i in range(len(b) - 1) :
        if( c[i] == 'B' and c[i + 1] == 'W'):
            c[i] = 'W'
            c[i + 1] ='B'
            n+=1
            J += 1
        else:
            pass
    if(J==0):flag = False
    J = 0


print(n)



### FIXED CODE ###

#coding: utf-8
a = input()

b = []
w = []
for i in range(len(a)):
    b.append(a[i])

for i in  range(len(a)):
    if (b[i] == 'W') :
        w.append(i)

n = 0
for i in range(len(w)):
    n += w[i] - i

print(n)
### BUGGY CODE ###

from sys import stdin, stdout
import math,sys,heapq
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
from os import path
import bisect as bi
def yes():print('YES')
def no():print('NO')
if (path.exists('input.txt')): 
    #------------------Sublime--------------------------------------#
    sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
    def I():return (int(input()))
    def In():return(map(int,input().split()))
else:
    #------------------PYPY FAst I/o--------------------------------#
    def I():return (int(stdin.readline()))
    def In():return(map(int,stdin.readline().split()))

def dict(a):
    d={}
    for x in a:
        if d.get(x,-1)!=-1:
            d[x]+=1
        else:
            d[x]=1
    return d

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bi.bisect_right(a, x)
    if i != len(a):
        return i
    else:            
        return -1

def main():
    try:
        n,k=In()
        l=list(In())   
        ans=[]
        t=1
        for x in range(k):
            t*=l[x]
        last=t
        i=k
        j=0
        while i<n:
            t*=l[i]
            t//=l[j]
            if t>last:
                ans.append('Yes')
            else:
                ans.append('No')
            last=t
            i+=1
            j+=1
        for x in ans:
            print(x)

    except:
        pass
        
M = 998244353
P = 1000000007
 
if __name__ == '__main__':
    #for _ in range(I()):main()
    for _ in range(1):main()




### FIXED CODE ###

from sys import stdin, stdout
import math,sys,heapq
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
from os import path
import bisect as bi
def yes():print('YES')
def no():print('NO')
if (path.exists('input.txt')): 
    #------------------Sublime--------------------------------------#
    sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
    def I():return (int(input()))
    def In():return(map(int,input().split()))
else:
    #------------------PYPY FAst I/o--------------------------------#
    def I():return (int(stdin.readline()))
    def In():return(map(int,stdin.readline().split()))

def dict(a):
    d={}
    for x in a:
        if d.get(x,-1)!=-1:
            d[x]+=1
        else:
            d[x]=1
    return d

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bi.bisect_right(a, x)
    if i != len(a):
        return i
    else:            
        return -1

def main():
    try:
        n,k=In()
        l=list(In())   
        ans=[]
        t=1
        last=1
        for x in range(k,n):
            if l[x-k]>=l[x]:
                print('No')
            else:
                print('Yes')


    except:
        pass
        
M = 998244353
P = 1000000007
 
if __name__ == '__main__':
    #for _ in range(I()):main()
    for _ in range(1):main()
### BUGGY CODE ###

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

B = [1]
i = 0
flag = False
for _ in range(N):
    if 2 in B:
        flag = True
        break
    elif A[i] in B:
        break
    B.append(A[i])
    i = A[i] - 1

print(len(B) - 1) if flag else print(-1)


### FIXED CODE ###

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

B = [1]
i = 0
cnt = 0
flag = False
for _ in range(N):
    i = A[i] - 1
    cnt += 1
    if i == 1:
        flag = True
        break

print(cnt) if flag else print(-1)
### BUGGY CODE ###

x=int(input())
i=j=0
while i**5-j**5-x:i=i%120+1;j=(j+99)%219-98
print(i,j)

### FIXED CODE ###

x=int(input())
[print(i,j)+exit()for i in range(200)for j in range(-i,i)if i**5-j**5==x]
### BUGGY CODE ###

s = input()
k = int(input())
arr = set()
arr.add(s)
for i in range(len(s)-1):
    for j in range(0, len(s)):
        arr.add(s[j:j+i+1])
arr = list(arr)
arr.sort()
print(arr[k-1])


### FIXED CODE ###

s = input()
k = int(input())
arr = set()
arr.add(s)
for i in range(len(s)-1):
    if i > 5:
        break
    for j in range(0, len(s)):
        arr.add(s[j:j+i+1])

arr = list(arr)
arr.sort()
print(arr[k-1])
### BUGGY CODE ###

N = int(input())
ARR = [int(s) for s in input().split(" ")]
def calculate(n,arr):
    result = ""
    if n % 2 == 0:
        for index,ar in enumerate(arr):
            if index % 2 == 0:
                if result == "":
                    result = result + str(ar)
                else:
                    result = result + " " + str(ar)
            else:
                if result == "":
                    result = str(ar) + result
                else:
                    result = str(ar) + " " + result
    else:
        for index,ar in enumerate(arr):
            if index % 2 == 0:
                if result == "":
                    result = str(ar) + result
                else:
                    result = str(ar) + " " + result
            else:
                if result == "":
                    result = result + str(ar)
                else:
                    result = result + " " + str(ar)




    return result

result = calculate(N,ARR)
print(result)

### FIXED CODE ###

N = int(input())
ARR = [int(s) for s in input().split(" ")]
def calculate(n,arr):

    left = list([])
    right = list([])
    if n % 2 == 0:
        for index,ar in enumerate(arr):
            if index % 2 == 0:
                right.append(str(ar))
            else:
                left.append(str(ar))
    else:
        for index,ar in enumerate(arr):
            if index % 2 == 0:
                left.append(str(ar))
            else:
                right.append(str(ar))

    left.reverse()
    left.extend(right)

    return left

result = calculate(N,ARR)
print(" ".join(result))
### BUGGY CODE ###

n,k=map(int,input().split())
s=[]
data=set(s)
for i in range(k):
    x,y=map(int,input().split())
    while(1):
        data.add(x)
        if(x>=y):
            break
        x+=1
        
dp=[0 for i in range(n+1)]
dp[1]=1
for i in range(1,n):
    for j in data:
        if(i+j<=n):
            dp[i+j]+=dp[i]
print(dp[n]%998244353)

### FIXED CODE ###

n,k=map(int,input().split())
dp=[0 for i in range(n+1)]
dp[1]=1
accum=[0 for i in range(n+1)]
accum[1]=1
s=[]
for i in range(k):
    x,y=map(int,input().split())
    s.append([x,y])
for i in range(2,n+1):
    for j in s:
        l,r=j
        tmpl=i-r
        tmpr=i-l
        if(tmpl<1):
            tmpl=1
        if(tmpr>=i):
            tmpr=i-1
        if(tmpr<0):
            continue
        dp[i]+=accum[tmpr]-accum[tmpl-1]
        dp[i]%=998244353
    accum[i]=dp[i]+accum[i-1]
    accum[i]%=998244353
print(dp[n]%998244353)
### BUGGY CODE ###

from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

if (X + Y) % 3 != 0:
    print(0)
    exit()

x_tmp=X+1
y_tmp=Y+2

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2 - 1

sum = x_count + y_count

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, sum + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ret = cmb(sum,x_count,mod)
print(ret)


### FIXED CODE ###

from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

if (X + Y) % 3 or not (X <= 2*Y and Y <= 2*X):
    print(0)
    exit()

x_tmp=X+1
y_tmp=Y+2

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2 - 1

sum = x_count + y_count

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, sum + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ret = cmb(sum,x_count,mod)
print(ret)
### BUGGY CODE ###

N,K = map(int,input().split())
array = []

for i in range(N):
    a,b = map(int,input().split())
    for i in range(b):
        array.append(a)
array.sort()
print(array[K-1])

### FIXED CODE ###

N,K = map(int,input().split())
array = []
sum = 0
for i in range(N):
    a,b = map(int,input().split())
    array.append([a,b])
array.sort(key = lambda x:x[0])
for i in range(N):
    sum += array[i][1]
    if sum >= K:
        print(array[i][0])
        exit()
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
MOD = 10 ** 9 + 7
A_max = A[K-1]
A_min = A[-K]
x = 1
count = 1
ans = A_max - A_min
for i in range(K,N):
    x = x * i // count
    #x %= MOD
    count += 1
    #print(x,i,count)
    A_tmp = ((A[i] - A[-1*i-1])* x) 
    #print(A_max,A_min)
    ans = (ans + A_tmp) % MOD
print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
mod = p = 10 ** 9 + 7

fact = [1]
fact_inv = [1]
for i in range(10**5+5):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
 
 
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod    

A_max = 0
A_min = 0
for i in range(N-K+1):
    A_max = (A_max + (A[(K-1)+i] * mod_comb_k((K+i-1),i,p))) % p   
    A_min = (A_min + (A[-1*(K+i)] * mod_comb_k((K+i-1),i,p))) % p
    #print(A_max,A_min,cmb((K+i),i,p))
ans = (A_max - A_min)
if ans < 0:
    ans = p + ans
ans %= p
print(ans)
### BUGGY CODE ###

k = int(input())
if k % 2 == 0:
    print(-1)
    exit()
modk = 7 % k
num = 0
for i in range(1,10**7):
    num = (num+modk)%k
    if num == 0:
        print(i)
        exit()
    modk = (modk * 10)%k
print(-1)

### FIXED CODE ###

k = int(input())
if k % 2 == 0:
    print(-1)
    exit()
modk = 7 % k
num = 0
for i in range(1,10**8):
    num = (num+modk)%k
    if num == 0:
        print(i)
        exit()
    modk = (modk * 10)%k
print(-1)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

AB=[]
for i in A:
  for j in B:
    AB.append(i+j)
AB=sorted(AB,key=lambda x: -x)
AB=AB[:min(K,len(A)*len(B))]
#print(AB)

ABC=[]
for i in AB:
  for j in C:
    ABC.append(i+j)
ABC=sorted(ABC,key=lambda x: -x)
#print(ABC)

for i in range(min(K,X*Y*Z)):
  print(ABC[i])

### FIXED CODE ###

import heapq

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

AB=[]
for i in A:
  for j in B:
    heapq.heappush(AB,-i-j)
#print(AB)

ABC=[]
for i in range(min(K,X*Y)):
  temp=heapq.heappop(AB)
  for j in C:
    heapq.heappush(ABC,temp-j)

for i in range(min(K,X*Y*Z)):
  print(-heapq.heappop(ABC))
### BUGGY CODE ###

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

mod = 10**9+7

def p(m,n):
    a = 1
    for i in range(n):
        a = a*(m-i)
    return a

def p_mod(m,n,mod):
    a = 1
    for i in range(n):
        a = a*(m-i) % mod
    return a

def c(m,n):
    return p(m,n) // p(n,n)

def c_mod(m,n,mod):
    return (p_mod(m,n,mod)*pow(p_mod(n,n,mod),mod-2,mod)) % mod

#各Aの元が何回max,minに採用されるかを考える

ans = 0
for i in range(N-K+1):
    ans -= (A[i]*c_mod(N-i-1,K-1,mod)) % mod

A.reverse()
for i in range(N-K+1):
    ans += (A[i]*c_mod(N-i-1,K-1,mod)) % mod

print(ans % mod)

### FIXED CODE ###

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

mod = 10**9+7


def p(m,n):
    a = 1
    for i in range(n):
        a = a*(m-i)
    return a

def p_mod(m,n,mod):
    a = 1
    for i in range(n):
        a = a*(m-i) % mod
    return a

def c(m,n):
    return p(m,n) // p(n,n)

def c_mod(m,n,mod):
    return (p_mod(m,n,mod)*pow(p_mod(n,n,mod),mod-2,mod)) % mod

C = [0]*(N-K+1)  #C[i] = (N-i-1)C_(K-1),予め二項係数を計算しておく
for i in range(N-K+1):
    if i == 0:
        C[i] = c_mod(N-1,K-1,mod)
    else:
        C[i] = (C[i-1]*(N-K-i+1)*pow(N-i,mod-2,mod)) % mod

#各Aの元が何回max,minに採用されるかを考える

ans = 0
for i in range(N-K+1):
    ans -= (A[i]*C[i]) % mod

A.reverse()
for i in range(N-K+1):
    ans += (A[i]*C[i]) % mod

print(ans % mod)
### BUGGY CODE ###

import itertools

N = int(input())
S = input()
L = []
for s in S:
    L.append(s)
P = []
for n in itertools.combinations(L, 3):
    o = ''
    for i in list(n):
        o += i
    P.append(o)
P = set(P)
print(len(P))

### FIXED CODE ###

N = int(input())
S = input()
cnt = 0
for i in range(1000):
    num = ''
    num += str(i // 100)
    num += str((i // 10) % 10)
    num += str(i % 10)
    j = 0
    for n in range(N):
        if S[n] == num[j]:
            j += 1
        if j == 3:
            break
    if j == 3:
        cnt += 1
print(cnt)
### BUGGY CODE ###

import itertools


N,M,R = map(int,input().split())
rs = list(map(lambda x:int(x)-1,input().split()))
cost=[[10**9]*N for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(i):  # j<i
            cost[i][j] =  min(cost[i][j],cost[i][k] + cost[k][j])
            cost[j][i] = cost[i][j]

ans = 10**9
for roads in itertools.permutations(rs):
    co = 0
    p = roads[0]
    for r in roads[1:]:
        co += cost[p][r]
        p = r
    ans = min(ans,co)
print(ans)


### FIXED CODE ###

import itertools
#TLE

N,M,R = map(int,input().split())
rs = list(map(lambda x:int(x)-1,input().split()))
cost=[[10**9]*N for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

for k in range(N):
    for i in range(N):
        for j in range(i):  # j<i
            cost[i][j] =  min(cost[i][j],cost[i][k] + cost[k][j])
            cost[j][i] = cost[i][j]

ans = 10**9
for roads in itertools.permutations(rs):
    co = 0
    p = roads[0]
    for r in roads[1:]:
        co += cost[p][r]
        p = r
    ans = min(ans,co)
print(ans)
### BUGGY CODE ###

n = int(input())
Ls = list(map(int, input().split()))
cnt = 0


def check(a, b, c):
    if a < b+c and b < c + a and c < a + b:
        return True
    else:
        return False

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if check(Ls[i], Ls[j], Ls[k]):
                cnt += 1
print(cnt)


### FIXED CODE ###

import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
from bisect import bisect_right
input = lambda: sys.stdin.readline().rstrip()


def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return


def main():
    n = int(input())
    Ls = list(map(int, input().split()))
    Ls.sort()
    cnt = 0
    for i in range(0,n-2):
        for j in range(i+1,n-1):
            #k以下なら良い
            k =  Ls[i] + Ls[j] -1
            # bisect_right(Ls, k)個の要素が左にある
            # 答え: bisect_right(Ls, k) - j
            cnt += max(bisect_right(Ls, k) - j-1, 0)
            # print(Ls, Ls[i],Ls[j],k, bisect_right(Ls,k)-j-1)
    print(cnt)
            

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

N=int(input())
a=[]
for i in range(N):
    a.append(int(input()))
minimum=1
count=0
while a:
   if(minimum<a[0]):
       count+=1
       if a[0] <= (minimum * 2) :
           a[0]=1
       else :
           a[0]-= minimum
   else:
       minimum=max(minimum,a[0]+1)
       a.pop(0)
print(count)


### FIXED CODE ###

N=int(input())
a=[0]*N
for i in range(N):
    a[i]=int(input())

minimum=2
count=a[0]-1
a.pop(0)
for i in  a:
   if(minimum<i):
       if i%minimum:
           count+= i//minimum
       else :
           count+= (i//minimum-1)
   else:
       minimum=max(minimum,i+1)
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
num = [0]*100000
s = sum(A)
for i in range(Q):
    B[i], C[i] = map(int,input().split())
for i in range(100000):
    num[i] = A.count(i+1)
for i in range(Q):
    s += (C[i]-B[i])*num[B[i]-1]
    print(s)
    num[C[i]-1] += num[B[i]-1]
    num[B[i]-1] = 0

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
cnt = [0]*100005
s = sum(A)
for i in A:
    cnt[i] += 1
for i in range(Q):
    B, C = map(int,input().split())
    s += (C-B)*cnt[B]
    print(s)
    cnt[C] += cnt[B]
    cnt[B] = 0
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = []
for i in range(Q):
    a = int(input())
    A.append(a)

for i in range(N):
    if K - (Q - A.count(i+1))> 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [K-Q]*N
for i in range(Q):
    a = int(input())
    A[a-1] += 1

for i in range(N):
    if A[i]> 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

a=int(input())
i=2
j=1
flag=0
x=0
y=0
min=a**0.5
intmin=int(min)

for i in range(intmin,a):
    if a%i == 0:
        if i!=a:
            print(int(i-2+(a/i)))
        else:
            print(a-1)
        break


# try:
#     for i in range(2,a//2):
#         mod=a%i
#         if mod==0:
#             if min > (a/i) + i -2:
#                 min = (a/i) + i -2
#     print(min)
# except ZeroDivisionError:
#     print("ZeroDivisionError!!")


### FIXED CODE ###

import math
import copy

n=int(input())

i=int(n**0.5)
j=0
# print(i)

for i in range(i+1,0,-1):
    # print(i)
    if n==i:
        print(n-1)
        break
    if n%i==0:
        j=n/i
        print(int(i+j-2))
        break
### BUGGY CODE ###




def main():
    N = int(input())
    S = list(input())
    ans = 0
    for i in range(N):
        first_s = S[i]
        for j in range(i+1, N):
            if S[j] != first_s:
                second_s = S[j]
                for k in range(j+1, N):
                    if (S[k] != first_s) and (S[k] != second_s):
                        if k == 2*j-i:
                            continue
                        ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

r, g, b = 0, 0, 0
ans = 0
for i in range(N):
    if S[i] == 'R':
        r += 1
    elif S[i] == 'G':
        g += 1
    else:
        b += 1

ans += r*g*b

for i in range(N):
    for j in range(i+1, N):
        if 2*j-i < N:
            if (S[i] != S[j]) and (S[j] != S[2*j-i]) and (S[i] != S[2*j-i]):
                ans -= 1

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

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
S=input()
L=len(S)
s=[0 for i in range(L)]
for i in range(L):
    if S[i]=="?":
        s[i]=10
    else:
        s[i]=int(S[i])

mod=10**9+7
K=modinv(10,13)
dp=[[0 for k in range(13)] for i in range(L)]
#dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
num=s[0]
if s[0]==10:
    for i in range(10):
        dp[0][i]=1
else:
    number=s[0]
    dp[0][number]=1

for i in range(1,L):
    if s[i]==10:
        for k in range(13):
            for j in range(10):
                dp[i][k]+=dp[i-1][((k-j)*K)%13]
        dp[i][k]=dp[i][k]%mod
    else:
        number=s[i]
        for k in range(13):
            dp[i][k]=dp[i-1][((k-number)*K)%13]
print(dp[L-1][5]%mod)


### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    #dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        for k in range(13):
            if s[i]=="?":
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            else:
                number=int(s[i])
                dp[i][k]=dp[i-1][U[k][number]]%mod
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()