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

import bisect
N = int(input())
A = list()
for i in range(N):
  A.append(int(input()))
L = list()
for j in range(N-1, -1, -1):
  n = A[j]
  if(len(L) == 0):
    L.append(n)
  elif(L[-1] <= n):
    L.append(n)
  else:
    x = bisect.bisect_right(L, n)
    L[x] = n
  L.sort()
print(len(L))

### FIXED CODE ###

import bisect
N = int(input())
A = list()
for i in range(N):
  A.append(int(input()))
L = list()
for j in range(N-1, -1, -1):
  n = A[j]
  if(len(L) == 0):
    L.append(n)
  elif(L[-1] <= n):
    L.append(n)
  else:
    x = bisect.bisect_right(L, n)
    L[x] = n
print(len(L))
### BUGGY CODE ###

N, M = map(int, input().split())
a = [0]*M
b = [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())
if N in b and 1 in a:
    for i in range(M):
        for j in range(M):
            if a[j] == 1 and b[i] == N and a[i] == b[j]:
                print('POSSIBLE')
                exit()
            else:
                pass
print('IMPOSSIBLE')

### FIXED CODE ###

n, m = map(int, input().split())
d = {i:[] for i in range(1, n)}
for i in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
ans = "IMPOSSIBLE"
for dd in d[1]:
    if n in d[dd]:
        ans = "POSSIBLE"
        break
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    tmp_max = max(a)
    del a[a.index(tmp_max)]
    a.append(tmp_max // 2)
print(sum(a))    

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a_minus = [-x for x in a]
import heapq
heapq.heapify(a_minus)
for i in range(m):
    nex_num = heapq.heappop(a_minus)
    nex_num = (-1 * nex_num) // 2 * -1
    heapq.heappush(a_minus, nex_num)
print(-sum(a_minus))
### BUGGY CODE ###

import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())
    P = [0] * N

    for i in range(N):
        P[i] = int(input())

    dp = [(0, 0)]

    for p in P:
        i = bisect_right(dp, (p, INF))
        if dp[i - 1][0] == p - 1:
            dp[i - 1] = (p, dp[i - 1][1] + 1)
        else:
            dp.insert(i, (p, 1))

    length = 1
    for _, l in dp:
        length = max(length, l)

    print(N - length)

sol()

### FIXED CODE ###

import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N = int(input())
    P = [0] * N

    for i in range(N):
        P[i] = int(input())

    pToIndex = {p : i for i, p in enumerate(P)}

    maxLeng = 1
    length = 1
    for n in range(1, N):
        if pToIndex[n] < pToIndex[n + 1]:
            length += 1
            maxLeng = max(maxLeng, length)
        else:
            length = 1

    print(N - maxLeng)

sol()
### BUGGY CODE ###

from collections import deque


def insert(ary, x):
    ary.appendleft(x)


def delete(ary, x):
    if x in ary:
        ary.remove(x)

def delete_first(ary):
    ary.popleft()


def delete_last(ary):
    ary.pop()


def operate(ary, op):
    cmd = op[0]

    if cmd == 'insert':
        x = int(op[1])
        insert(ary, x)
    elif cmd == 'delete':
        x = int(op[1])
        delete(ary, x)
    elif cmd == 'deleteFirst':
        delete_first(ary)
    elif cmd == 'deleteLast':
        delete_last(ary)


n = int(input())
ary = deque([])

[operate(ary, input().split()) for i in range(n)]
print(*ary)



### FIXED CODE ###

import sys
from collections import deque

n = int(input())
ary = deque([])

for line in sys.stdin:
    op = line.strip().split()
    cmd = op[0]

    if cmd == 'insert':
        x = op[1]
        ary.appendleft(x)

    elif cmd == 'delete':
        x = op[1]
        if x in ary:
            ary.remove(x)

    elif cmd == 'deleteLast':
        ary.pop()

    else:
        ary.popleft()

print(*ary)
### BUGGY CODE ###

import sys
N = int(input())
A = [int(n) for n in input().split()]
MAX = 10**18
ans = 1
for a in A:
    ans *= a
else:
    if ans > MAX:
        print("-1")
    else:
        print(ans)

### FIXED CODE ###

import sys
N = int(input())
A = [int(n) for n in input().split()]
MAX = 10**18
ans = 1
if 0 in A:
    print("0")
    sys.exit()
for a in A:
    if ans > MAX:
        print("-1")
        sys.exit()
    ans *= a
else:
    if ans > MAX:
        print("-1")
    else:
        print(ans)
### BUGGY CODE ###

N = int(input())
A = []
B = []
for _ in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)

a = b = 0
for i in range(N):
  if i % 2 == 0: #高橋くんの番
    x, y = A, B
  else:#青木さんの番
    x, y = B, A
  indexes = [i for i, j in enumerate(y) if j == max(y)] #yの最大値のインデックスすべて
  l = len(indexes)
  m = 0
  ind = 0
  for j in indexes: #このうちxで最大値を取るインデックス
    if x[j] > m:
      m = x[j]
      ind = j
  if i % 2 == 0: a += x[ind]
  else: b += x[ind]
  x[ind] = y[ind] = 0
print(a-b)

### FIXED CODE ###

import numpy as np
n = int(input())
A,B = np.array([input().split() for _ in range(n)], dtype=np.int64).T

ans = A.sum() #全部先手が取る
improve = A+B #後手がとると改善する量
improve.sort()
ans -= improve[::-1][1::2].sum()
print(ans)
### BUGGY CODE ###

import copy

n = int(input())
a = list(map(int,input().split()))
b = [0]

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

del b[0]

c = copy.copy(b)

first_minus = 0
first_plus = 0

for i in range(len(b)):
    if(i%2 == 0):
        if (b[i] >= 0):
            diff =  abs(b[i]) + 1
            first_minus = first_minus +  diff
            b = list(map(lambda x: x - diff, b))

        if (c[i] <= 0):
            diff =  abs(c[i]) + 1
            first_plus = first_plus +  diff
            c = list(map(lambda x: x + diff, c))
    else:
        if (b[i] <= 0):
            diff =  abs(b[i]) + 1
            first_minus = first_minus +  diff
            b = list(map(lambda x: x + diff, b))

        if (c[i] >= 0):
            diff =  abs(c[i]) + 1
            first_plus = first_plus +  diff
            c = list(map(lambda x: x - diff, c))

print(min(first_minus,first_plus))

### FIXED CODE ###

import copy

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

ans_a = 0
for i in range(len(a)):
    sum += a[i]
    if(i%2 == 0):
        if(sum >= 0):
            ans_a += sum + 1
            sum = -1
    else:
        if(sum <= 0):
            ans_a += 1 - sum
            sum = 1

sum = 0
ans_b = 0
for i in range(len(a)):
    sum += a[i]
    if(i%2 == 0):
        if(sum <= 0):
            ans_b += 1 - sum
            sum = 1
    else:
        if(sum >= 0):
            ans_b += sum + 1
            sum = -1

print(min(ans_a,ans_b))
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i, a in enumerate(A):
    A[i] = -a
A.sort()
h = []
"""
Contain in lst the pair (a+b, a, b) such that a+b gets smaller monotonically
At this stage we identify (a, b) with (b, a)
"""
for i in range(N):
    a = -A[i]
    for j in range(i, N):
        b = -A[j]
        heapq.heappush(h, (-a-b, a, b))

happy = 0
times = 0
while times < M:
    s, a, b = heapq.heappop(h)
    if a == b:
        happy -= s
        times += 1
    else:
        if times < M - 1:
            happy -= s * 2
            times += 2
        else:
            happy -= s
            times += 1

print(happy)


### FIXED CODE ###

import sys
from bisect import bisect_left, bisect_right
import itertools

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
#print("A={}".format(A))
"""
この問題の前半は、合計の幸福度Xが上位M個未満に入るかを判定する。
    -> Xに関する二分探索をすることで、上位から丁度M番目の幸福度がわかる！

これを判定するために、左手の握手先をfix(A[i]とする)して、
右手の幸福度が(X - A[i])以上であるものの個数を数える。
"""

def within(X, M):
    """
    幸福度がX以上上がるような握手の組がM個未満ならTrue、そうでなければFalseを返す
    """
    pair = 0
    for i in range(N):
        idx = bisect_left(A, X - A[i])
        pair += N - idx
    if pair < M:
        #print("pair={}<M".format(pair))
        return True
    else:
        #print("pair={}>=M".format(pair))
        return False

"""
Xに関する二分探索をおこなった結果、
leftXはwithin(leftX, M) == Trueになる最小のX
"""
leftX = 0
rightX = A[-1] * 2 + 1
while leftX != rightX:
    middleX = (leftX + rightX) // 2
    #print("mid={}".format(middleX))
    if within(middleX, M):
        rightX = middleX
    else:
        leftX = middleX + 1
#print("leftX={}".format(leftX))

"""
これより後半、幸福度の総和を求める。
前半同様に左手をfixした上で、両手の幸福度の合計がleftX以上になるときの幸福度を加算していく。
単純に右手に関してfor文を回して加算するとTLEなので、
右手の幸福度に関しては先に累積和を求めておく。
"""
S = list(itertools.accumulate(A))
#print("S={}".format(S))
happy = 0
times = 0
for i in range(N):
    idx = bisect_left(A, leftX - A[i])
    times += N - idx
    #print("When i={}, idx={}, times={}".format(i, idx, times))
    if idx != 0:
        happy += A[i] * (N - idx) + (S[-1] - S[idx - 1])
    else:
        happy += A[i] * (N - idx) + S[-1]
    #print("happy={}".format(happy))
happy += (leftX - 1) * (M - times)

print(happy)
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.5 : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-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()))
tmp = []
for a in A:
    for b in B:
        tmp.append(a + b)
ans = []
for ab in tmp:
    for c in C:
        ans.append(ab + c)
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])


### FIXED 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()))

# A+Bの上位K個
tmp = []
for a in A:
    for b in B:
        tmp.append(a + b)
tmp.sort(reverse=True)
tmp = tmp[:K]

ans = []
for ab in tmp:
    for c in C:
        ans.append(ab + c)
ans.sort(reverse=True)

for i in range(K):
    print(ans[i])
### BUGGY CODE ###

k,s = map(int, input().split())
ans = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int, input().split())
cnt = 0
for i in range(k+1):
    for j in range(k+1):
        z = s - i - j
        if z >= 0 and z <= k:
            cnt+=1
print(cnt)
### BUGGY CODE ###

import itertools
from collections import deque

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

ans = [-1] * N
ans[0] = 0
d = deque([1])
while any(i == -1 for i in ans) and any(i != [-1, -1] for i in AB):
    now = d[0]
    for i in itertools.product(range(M), range(2)):
        if AB[i[0]][i[1]] == now:
            if ans[AB[i[0]][1 - i[1]] - 1] == -1:
                ans[AB[i[0]][1 - i[1]] - 1] = now
                d.append(AB[i[0]][1 - i[1]])
            AB[i[0]] = [-1, -1]
    d.popleft()

if any(i == -1 for i in ans):
    print('No')
else:
    print('Yes')
    for i in ans[1:]:
        print(i)


### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
g = [[] for i in range(N)]
for i in range(M):
    A, B = map(int, input().split())
    g[A-1].append(B)
    g[B-1].append(A)

ans = [-1] * N
ans[0] = 0
d = deque([1])
while len(d) != 0:
    now = d[0]
    d.popleft()
    for i in g[now-1]:
        if ans[i-1] != -1:
            continue
        ans[i-1] = now
        d.append(i)

if -1 in ans:
    print('No')
else:
    print('Yes')
    for i in ans[1:]:
        print(i)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=sum(A)
s=N+1
j=s

if A==sorted(A):
    print(0)
    exit()

for i in range(N):
    x=max(A[:s])
    s=A.index(x)
    A[s:j]=[x]*len(A[s:j])
    j=s
    if  A==sorted(A):
        break

print(sum(A)-ans)

### FIXED CODE ###

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

for i in range(1,N):
    if A[i-1] > A[i]:
        A[i]=A[i-1]

print(sum(A)-ans)
### BUGGY CODE ###

#D 復習
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
whole_sum = (2 ** n % mod) - 1

def combinations_mod(n, k, mod):
    X, Y = 1, 1
    for i in range(1, k+1):
        X = (X * (n-i+1))%mod
    for j in range(1, k+1):
        Y = (Y*j)%mod
    result = X * (pow(Y, mod-2, mod))
    return result%mod

whole_sum -= combinations_mod(n, a, mod)
whole_sum -= combinations_mod(n, b, mod)

print(whole_sum % mod)


### FIXED CODE ###

#D 復習
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
whole_sum = pow(2, n, mod) - 1

def combinations_mod(n, k, mod):
    X, Y = 1, 1
    for i in range(1, k+1):
        X = (X * (n-i+1))%mod
    for j in range(1, k+1):
        Y = (Y*j)%mod
    result = X * (pow(Y, mod-2, mod))
    return result%mod

whole_sum -= combinations_mod(n, a, mod)
whole_sum -= combinations_mod(n, b, mod)

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

N,K=map(int,input().split())
p=list(map(int,input().split()))
Max=0
for i in range(N+1-K):
    a=0
    for j in range(K):
        a+=(1+p[i+j])/2
    if Max<a:
        Max=a
print(Max)

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
a=0
for j in range(K):
    a+=(1+p[j])/2
Max=a
for i in range(K,N):
    a=a+(p[i]-p[i-K])/2
    if Max<a:
        Max=a
print(Max)
### BUGGY CODE ###

N = input()
P_list = input().split()
# N = '5'
# P_list = '4 2 5 1 3'.split()
P_list = [int(i) for i in P_list]
length = int(N)
ans = 0 
M = []
for i in range(length):
    # print(min(P_list[0:i+1]))
    if P_list[i]==min(P_list[0:i+1]):
        ans +=1
    
print(ans)

### FIXED CODE ###

N = input()
P_list = input().split()
# N = '5'
# P_list = '4 2 5 1 3'.split()
P_list = [int(i) for i in P_list]
length = int(N)
ans = 0 
M = []
mini =-1
for i in range(length):
    # print(min(P_list[0:i+1]))
    if P_list[i] <mini or mini <0:
        mini = P_list[i]
    if mini == P_list[i]:
        ans +=1


    # if P_list[i]==min(P_list[0:i+1]):
    #     ans +=1
    
print(ans)
### BUGGY CODE ###

N = int(input())
L = [input()]

for _ in range(N-1):
    a = input()
    imin = 0
    imax = len(L)-1

    while (imin<imax):
        l = (imin+imax)//2
        if (a==L[l]):
            break
        elif (a>L[l]):
            imin = l
        else:
            imax = l
    
    if (a>L[imin]):
        L.insert(imin+1,a)
    elif (a<L[imin]):
        L.insert(imin,a)
            
print(len(L))

### FIXED CODE ###

N = int(input())
L = set([input() for _ in range(N)])
print(len(L))
### BUGGY CODE ###

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

ans = 1

for i in A:
    ans *= i

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

A = sorted(A, reverse= True)

if A[-1] == 0:
    print(0)
    exit()
    
ans = 1

for i in A:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit()

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

N,K,Q = map(int,input().split())
A = [input() for _ in range(Q)]
for i in range(1,N+1):
  a = A.count(str(i))
  if  K - (Q - a) > 0:
    print('Yes')
  else:
    print('No')


### FIXED CODE ###

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

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

n=int(input())

def f(a,b):
    return max(len(str(a)),len(str(b)))
m=10000
for a in range(1,10**10):
    if n%a==0:
        m=min(f(a,n//a),m)
    if n<a:
        break
print(m)

### FIXED CODE ###

#n, *d = map(int, open(0).read().split())
# dream dreamer erase eraser 
n=int(input())

def f(a,b):
    return max(len(str(a)),len(str(b)))
m=10000
for a in range(1,10**10):
    if n%a==0:
        m=min(f(a,n//a),m)
    if n<a or n//a<a:
        break
print(m)
### BUGGY CODE ###

import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

tmp = 1
for i in a:
  if tmp%i == 0:
    continue
  tmp = i*tmp//fractions.gcd(i, tmp)

ans = 0
for i in a:
  ans += tmp//i
#print(tmp)
print(ans %mod)


### FIXED CODE ###

import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

tmp = 1
for i in a:
  tmp = (i//fractions.gcd(i, tmp)) * tmp

ans = 0
for i in a:
  ans += tmp//i
#print(tmp)
print(ans %mod)
### BUGGY CODE ###

import math
k = int(input())

ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for s in range(1,k+1):
            ans += math.gcd(math.gcd(i,j),s)

print(ans)

### FIXED CODE ###

k = int(input())

ans = 0
def gcd(x,y):
    while y:
        x, y = y, x % y
    return x

for i in range(1,k+1):
    for j in range(1,k+1):
        for s in range(1,k+1):
            ans += gcd(gcd(i,j),s)

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

N = int(input())
p = list(map(int, input().split()))
sum = [i + 1 + x for i, x in enumerate(p)]
dif = [i + 1 - x for i, x in enumerate(p)]
ans = 0

for i in range(N):
    for j in range(i + 1, N):
        if dif[j] == sum[i]:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
p = list(map(int, input().split()))
d = defaultdict(int)
ans = 0

for i in range(N):
    ans += d[i + 1 - p[i]]
    d[i + 1 + p[i]] += 1

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

K = int(input())
Judge = True
remain_initial = 7 % K
remain = 0
i = 0

while Judge == True:
    i += 1
    remain_str = str(remain) + '7'
    number = int(remain_str)
    remain = number % K

    if number % K == 0:
        Judge = False
        answer = i

    elif i == 1:
        continue

    elif number % K == remain_initial:
        Judge = False
        answer = -1

print(answer)

### FIXED CODE ###

K = int(input())
remain = 0
i = 0

answer = -1

for i in range(1, K+5):
    number = remain*10 + 7

    remain = number % K

    if remain == 0:
        answer = i
        break

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

n, k = map(int,input().split())
p = list(map(int,input().split()))
expect = []
ans = 0
for i in p:
    expect.append((1 + i)/2)

for i in range(n-k+1):
    tmp = sum(expect[i : i + k])
    ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

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

sum_p =[0]
tmp = 0
for i in p:
    tmp += i
    sum_p.append(tmp)

max_expect = 0
for i in range(k, n+1):
    tmp = sum_p[i] - sum_p[i - k]
    max_expect = max(tmp, max_expect)

ans = (k + max_expect)/2
print(ans)
### BUGGY CODE ###

power = 1
n = int(input())
tmp = 10 ** 9 + 7

for i in range(n):
    power = power * (i + 1)

power = power % tmp
print(power)

### FIXED CODE ###

power = 1
n = int(input())
tmp = 10 ** 9 + 7

for i in range(n):
    power = power * (i + 1) % tmp

print(power)
### BUGGY CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

ans = 0

for i in range(N - 2):

  S2 = []
  for j in range(N - i - 2):
    rgb = "RGB"
    if S[i] == S[i + j + 1]:
      continue
    rgb = rgb.replace(S[i], "")
    rgb = rgb.replace(S[i + j + 1], "")
    if i + ((j + 1) * 2) < N:
      S2 = S[i + j + 2:i + (2 * j) + 2] + S[i + (2 * j) + 3:]
    else:
      S2 = S[i + j + 2:]
    ans += S2.count(rgb)

print(ans)


### FIXED CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

R = S.count("R")
G = S.count("G")
B = S.count("B")

cnt = 0

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

print(R * G * B - cnt)
### BUGGY CODE ###

def floor(a, b):
    return (-a)//b*(-1)


def inc_list(i, l):
    if i >= len(l):
        print("err")
        return l
    for j in range(i):
        l[j] += 1
    return l


def inc_mult(i, n, l):
    for _ in range(n):
        l = inc_list(i, l)
    return l


N = int(input())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)


ans = 0
for i in reversed(range(N)):
    a = A[i]
    b = B[i]
    inc = floor(a, b)*b - a
    A = inc_mult(i, inc, A)
    ans += inc

print(ans)


### FIXED CODE ###

def floor(a, b):
    return (-a)//b*(-1)


N = int(input())
A = []
B = []
total_add = 0
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)


ans = 0
for i in reversed(range(N)):
    a = A.pop(-1)
    a += total_add
    b = B.pop(-1)
    inc = b*floor(a, b)-a
    total_add += inc

print(total_add)
### BUGGY CODE ###

n, m = map(int, input().split())
gates = []
for _ in range(m):
    l, r = map(int, input().split())
    #gates.append(list(range(l-1, r)))
    gates.append([l-1, r])

res = 0
for i in range(n):
    flag = False
    for j in range(m):
        if gates[j][0] <= i < gates[j][1]:
            flag = True
        else:
            flag = False
            break
    
    if flag == True:
        res += 1

print(res)

### FIXED CODE ###

n, m = map(int, input().split())
L, R = [], []
for _ in range(m):
    l,r = map(int, input().split())
    L.append(l)
    R.append(r)


res = min(R) - max(L) + 1
if res < 0:
    print(0)
else:
    print(res)
### BUGGY CODE ###

import math
N=int(input())
A=list(map(int,input().split()))
ans1 = A[0]
ans2 = 0
f = True
for i in range(1, N):
    ans1 = math.gcd(ans1, A[i])
    for j in range(i+1, N):
        ans2 = math.gcd(A[i-1],A[j-1])
        if (ans2 > 1):
            f = False
            break
    if f==False and ans1 ==1:
        break


if f:
    print('pairwise coprime')
else:
    if ans1==1:
        print('setwise coprime')
    else:
        print('not coprime')


### FIXED CODE ###

from math import gcd

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

# setwise validation
tmp = 0
for a in A:
    tmp = gcd(tmp, a)
isSetwise = (tmp == 1)

# pairwise validation
M = 10 ** 6
sieve = [0] * (M + 1)
for a in A:
    sieve[a] += 1

cnt = 0
isPairwise = True
for i in range(2, M + 1):
    isPairwise &= (sum(sieve[j] for j in range(i, M + 1, i)) <= 1)

# check
if isPairwise:
    ans = 'pairwise coprime'
elif isSetwise:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)