CodeEff/ECCO huggingface dataset:
# Original solution
n = int(eval(input()))
a = []
for i in range(n):
    a.append(int(eval(input())))

import bisect
from collections import deque

lis = deque()
for i in range(n):
    ind = bisect.bisect_left(lis,a[i])
    if ind==0:
        lis.appendleft(a[i])
    else:
        lis[ind-1] = a[i]

print((len(lis)))


# Optimized solution
import sys
def input():
    return sys.stdin.readline()[:-1]
n = int(eval(input()))
a = []
for i in range(n):
    a.append(int(eval(input())))

import bisect
from collections import deque

lis = deque()
for i in range(n):
    ind = bisect.bisect_left(lis,a[i])
    if ind==0:
        lis.appendleft(a[i])
    else:
        lis[ind-1] = a[i]

print((len(lis)))
# Original solution
import bisect
n = int(eval(input()))
a = [int(eval(input())) for i in range(n)]
ans = 0
color = [a[n-1]]
for i in range(n-2,-1,-1):
    x = bisect.bisect_right(color,a[i])
    if x == len(color):
        color.append(a[i])
    else:
        color[x] = a[i]
print((len(color)))

# Optimized solution
import bisect
n = int(eval(input()))
a = [int(eval(input())) for i in range(n)]
ans = 0
color = [a[n-1]]
for i in range(n-2,-1,-1):
    if a[i]>=color[-1]:
        color.append(a[i])
    else:
        x = bisect.bisect_right(color,a[i])
        color[x] = a[i]
print((len(color)))
# Original solution
import bisect

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]
# それぞれの色の最大値を入れる筒のリスト
t = []

for i in a:
    # それぞれの色のどの値よりも小さかったとき
    idx = bisect.bisect_left(t, i)
    # print(i, idx)
    if idx == 0:
        t.insert(0, i)
    # 効率的な色の探索
    else:
        t[idx-1] = i
    # print(t)

print((len(t)))

# Optimized solution
import bisect

n = int(eval(input()))
a = [int(eval(input())) for _ in range(n)]
# それぞれの色の最大値を入れる筒のリスト
t = [a[-1]]

for i in reversed(a[:-1]):
    # それぞれの色のどの値よりも小さかったとき
    idx = bisect.bisect_left(t, i+1)
    # print(i, idx)
    if idx == len(t):
        t.append(i)
    # 効率的な色の探索
    else:
        t[idx] = i
    # print(t)

print((len(t)))
# Original solution
#%%
import bisect

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

ans_list = []
for i in range(n):
    tmp = bisect.bisect_left(ans_list, a[i])
    #print(tmp)
    if tmp == 0:
        ans_list.insert(0, a[i])
    else:
        ans_list[tmp-1] = a[i]
    #print(ans_list)
print((len(ans_list)))

    


# Optimized solution
#%%
import bisect

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

ans_list = [-1] * n
for i in range(n):
    tmp = bisect.bisect_left(ans_list, a[i])
    #print(tmp)
    if tmp == 0:
        ans_list.insert(0, a[i])
    else:
        ans_list[tmp-1] = a[i]
    #print(ans_list)

ans = 0
for i in range(n):
    if ans_list[i] != -1:
        ans += 1
print(ans)
# Original solution
from bisect import bisect_left
n = int(eval(input()))
ans = [int(eval(input()))]
for i in range(n-1):
    now = int(eval(input()))
    j = bisect_left(ans,now)
    if j == 0:
        ans.insert(0,now)
    else:
        ans[j-1] = now

print((len(ans)))

# Optimized solution
def bisect_right(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 lo

n = int(eval(input()))
f = int(eval(input()))
ans = [-f]
for i in range(n-1):
    now = -int(eval(input()))
    j = bisect_right(ans,now)
    if j == len(ans):
        ans.append(now)
    else:
        ans[j] = now

print((len(ans)))
# Original solution
def bisect_right(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 lo

n = int(eval(input()))
f = int(eval(input()))
ans = [-f]
for i in range(n-1):
    now = -int(eval(input()))
    j = bisect_right(ans,now)
    if j == len(ans):
        ans.append(now)
    else:
        ans[j] = now

print((len(ans)))


# Optimized solution
from bisect import bisect_right
n = int(eval(input()))
ans = 1
data = [-int(eval(input()))]
for i in range(n-1):
    x = -int(eval(input()))
    j = bisect_right(data,x)
    if j == ans:
        data.append(x)
        ans += 1
    else:
        data[j] = x
print(ans)
# Original solution
import bisect
N = int(eval(input()))
A = [int(eval(input()))for _ in range(N)]
li = [-1]
for i in A[::-1]:
    if(max(li)<i):
        li.append(i)
    else:
        ind = bisect.bisect_right(li,i)
        if(ind>=len(li)):
            li.append(i)
        elif(li[ind]>i):
            li.pop(ind)
            li.insert(ind,i)
        else:
            li.pop(ind+1)
            li.insert(ind+1)
print((len(li)-1))

# Optimized solution
import bisect
N = int(eval(input()))
A = [int(eval(input()))for _ in range(N)]
li = [-1]
for i in A[::-1]:
    if(li[-1]<i):
        li.append(i)
    else:
        ind = bisect.bisect_right(li,i)
        if(ind>=len(li)):
            li.append(i)
        elif(li[ind]>i):
            li.pop(ind)
            li.insert(ind,i)
        else:
            li.pop(ind+1)
            li.insert(ind+1)
print((len(li)-1))
# Original solution
import sys
from bisect import bisect_left

input = sys.stdin.readline


def main():
    N = int(eval(input()))
    A = [0] * N
    for i in range(N):
        A[i] = int(eval(input()))

    colors = []
    for a in A:
        idx = bisect_left(colors, a)
        if idx == 0:
            colors.insert(0, a)
        else:
            colors[idx - 1] = a

    ans = len(colors)
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import sys
from bisect import bisect_right

input = sys.stdin.readline


def main():
    N = int(eval(input()))
    A = [0] * N
    for i in range(N):
        A[i] = int(eval(input()))

    A = [-a for a in A]

    colors = []
    for a in A:
        idx = bisect_right(colors, a)
        if idx == len(colors):
            colors.append(a)
        else:
            colors[idx] = a

    ans = len(colors)
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
n=int(eval(input()))
# 降順のリストで二分探索
# 自分より小さい数字で最も大きいものを自分でアップデート
# 該当がなければ最後に追加
d=[]
d.append(int(eval(input())))
for i in range(n-1):
  a=int(eval(input()))
  ok=len(d)
  ng=-1
  while abs(ok-ng)>1:
    mid=abs(ok+ng)//2
    if d[mid]<a:
      ok=mid
    else:
      ng=mid
  if ok==len(d):
    d.append(a)
  else:
    d[ok]=a
print((len(d)))

# Optimized solution
import sys
readline = sys.stdin.readline

N = int(readline())
ans = []
import bisect
for i in range(N):
  a = -int(readline())
  ind = bisect.bisect_right(ans, a)
  if ind == len(ans):
    ans.append(a)
  else:
    ans[ind] = a
    
print((len(ans)))
# Original solution
#54 ABC134E

n=int(eval(input()))
a=[int(eval(input())) for _ in range(n)]

import heapq
i=0
heap=[-a[0]]
res=[]
import bisect
for i in range(1,n):
	t=bisect.bisect_right(heap,-a[i])
	if t==0:
		heapq.heapreplace(heap,-a[i])
	elif t>=len(heap):
		heapq.heappush(heap,-a[i])
	else:
		heap[t]=-a[i]
		heapq.heapify(heap)

	#print(heap,t)
print((len(heap)))

# Optimized solution
#54 ABC134E

n=int(eval(input()))
a=[int(eval(input())) for _ in range(n)]

def LIS(L):
    from bisect import bisect
    seq=[]
    for i in L:
        pos=bisect(seq,-i)
        if len(seq)<=pos:
            seq.append(-i)
        else:
            seq[pos]=-i
    return len(seq)

print((LIS(a)))
# Original solution
import sys
from bisect import bisect_left
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(readline())
A = list(map(int, read().split()))

a = [-1] * N

for i in A:
    n = bisect_left(a, i)
    a[n - 1] = i

print((N - a.count(-1)))

# Optimized solution
import sys
from bisect import bisect_left
read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N, *A = list(map(int, read().split()))

    a = [-1] * N

    for i in A:
        n = bisect_left(a, i)
        a[n - 1] = i

    print((N - a.count(-1)))


if __name__ == '__main__':
    main()
# Original solution
import bisect
from collections import deque
N = int(eval(input()))
nums = [int(eval(input())) for _ in range(N)]
# i<jで、 AiとAjが同じ色で塗られている場合、Ai < Ajが成り立つ.
# その際に、色の最小数をだす。
LIS = deque([nums[0]])
count = 0
for index, num in enumerate(nums):
    if index == 0:
        continue
    if num <= LIS[0]:
        LIS.appendleft(num)
    else:
        insert_index = bisect.bisect_left(LIS, num)
        LIS[insert_index - 1] = num
print((len(LIS)))


# Optimized solution
import bisect
from collections import deque
N = int(eval(input()))
nums = deque([])

for i in range(N):
    num = int(eval(input()))
    if i == 0:
        nums.append(num)
    else:
        if nums[-1] < num:
            nums[-1] = num
        else:
            insert_index = bisect.bisect_left(nums, num)
            if insert_index == 0:
                nums.appendleft(num)
            else:
                nums[insert_index - 1] = num
#     print(nums)
# print(nums)
print((len(nums)))
# Original solution
from sys import stdin, setrecursionlimit
from bisect import bisect_right

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(eval(input()))
    A = tuple(int(eval(input())) for _ in range(N))
    B = [-A[0]]

    for a in A[1:]:
        if a <= -B[-1]:
            B.append(-a)
        else:
            B[bisect_right(B, -a)] = -a

    print((len(B)))


if __name__ == '__main__':
    main()


# Optimized solution
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = list(map(int, read().split()))

    A.reverse()

    dp = [A[0]]
    for a in A[1:]:
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a

    print((len(dp)))
    return


if __name__ == '__main__':
    main()
# Original solution
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = list(map(int, read().split()))

    vec = [INF] * N
    for a in reversed(A):
        vec[bisect_right(vec, a)] = a

    print((N - vec.count(INF)))
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys
from bisect import bisect_right

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = list(map(int, read().split()))

    vec = [INF] * N
    for a in reversed(A):
        vec[bisect_right(vec, a)] = a

    try:
        print((vec.index(INF)))
    except:
        print(N)

    return


if __name__ == '__main__':
    main()
# Original solution
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(eval(input()))
    seq = [int(eval(input())) for _ in range(n)]

    # リストseqからLISの長さを出す

    import bisect
    
    def main():
        cnt=0
        while len(seq)>0:

            LIS = [seq[0]]
            for i in range(len(seq)):
                if seq[i] > LIS[-1]:
                    LIS.append(seq[i])
                else:
                    LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
            cnt+=1
            
            for i in LIS:
                seq.remove(i)
        return cnt
    print((main()))
    




resolve()

# Optimized solution
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(eval(input()))
    seq = [int(eval(input())) for _ in range(n)][::-1]

    """
    Longest Increasing/Decreasing Subsuquence (LIS, LDS)
    Verified:
        https://atcoder.jp/contests/abc134/tasks/abc134_e
        https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_D
    """


    def longest_subsequence(A: "Array[int]", equals: bool, increasing: bool) -> int:
        """
        Compute the length of LIS or LDS.
        
        Args:
            A ("Array[int]"): a list or tuple to compute.
            equals (bool): permit adjacent numbers in subsequence to equal.
            increasing (bool): compute an increasing subsequence or decreasing one.
        Returns: (int) the length of a subsequence.
        """
        from bisect import bisect_left, bisect_right

        bs = bisect_right if equals else bisect_left
        compare = (lambda x, y: x >= y) if equals else (lambda x, y: x > y)
        if not increasing:
            A = A[::-1]

        dp = [A[0]]  # dp := length of LIS (dp table itself is not LIS)
        for i in A[1:]:
            if compare(i, dp[-1]):
                dp.append(i)
            else:
                dp[bs(dp, i)] = i
        return len(dp)
    
    print((longest_subsequence(seq,True,True)))

    
    




resolve()
# Original solution
import bisect
N=int(eval(input()))
A=[int(eval(input())) for _ in range(N)]
color=[]
for a in A:
    i=bisect.bisect_left(color,a)
    if i==0:
        color.append(a)
    else:
        color[i-1]=a
    color.sort()
print((len(color)))

# Optimized solution
import bisect
N=int(eval(input()))
A=[int(eval(input())) for _ in range(N)]
color=[-1]*(N)
for a in A:
    i=bisect.bisect_left(color,a)
    color[i-1]=a
print((N-bisect.bisect_right(color,-1)))
# Original solution
def solve(string):
    *nkrsp, t = string.split()
    *t, = list(map(int, t.replace("r", "2").replace("s", "0").replace("p", "1")))
    n, k, *rsp = list(map(int, nkrsp))
    ans = 0
    for s in range(k):
        u = t[s::k]
        i = 0
        while i < len(u):
            c = 1
            while i < len(u) - 1 and u[i] == u[i + 1]:
                i += 1
                c += 1
            ans += (c + 1) // 2 * rsp[u[i]]
            i += 1
    return str(ans)


if __name__ == '__main__':
    import sys
    print((solve(sys.stdin.read().strip())))


# Optimized solution
def solve(string):
    *nkrsp, t = string.split()
    n, k, *rsp = list(map(int, nkrsp))
    table = {k: v for k, v in zip("spr", rsp)}
    ans = 0
    for s in range(k):
        u = t[s::k]
        i = 0
        while i < len(u):
            c = 1
            while i < len(u) - 1 and u[i] == u[i + 1]:
                i += 1
                c += 1
            ans += (c + 1) // 2 * table[u[i]]
            i += 1
    return str(ans)


if __name__ == '__main__':
    import sys
    print((solve(sys.stdin.read().strip())))
# Original solution
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, R: int, S: int, P: int, T: str):
    ans=0
    flag=[False]*N
    for i in range(N):
        if i<K:
            ans+=P if T[i]=='r' else S if T[i]=='p' else R
            flag[i]=True
    for i in range(K, N):
        if T[i]!=T[i-K] or (not flag[i-K]):
            ans+=P if T[i]=='r' else S if T[i]=='p' else R
            flag[i]=True
        
    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    T = next(tokens)  # type: str
    solve(N, K, R, S, P, T)

if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys


def solve(N: int, K: int, R: int, S: int, P: int, T: str):
    ans=0
    flag=[False]*N
    for i in range(N):
        if i<K or T[i]!=T[i-K] or (not flag[i-K]):
            ans+=P if T[i]=='r' else S if T[i]=='p' else R
            flag[i]=True
        
    print(ans)

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    R = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    T = next(tokens)  # type: str
    solve(N, K, R, S, P, T)

if __name__ == '__main__':
    main()
# Original solution
N, K = list(map(int, input().strip().split()))
R, S, P = list(map(int, input().strip().split()))
score = {}
score['r'] = P
score['s'] = R
score['p'] = S
T = input().strip()

i = 0
skipl = []
res = 0
while i < N:
    if i in skipl:
        i += 1
        continue
    if i+K < N and T[i+K] == T[i]:
        skipl.append(i+K)
    res += score[T[i]]
    i += 1

print(res)

# Optimized solution
N, K = list(map(int, input().strip().split()))
R, S, P = list(map(int, input().strip().split()))
score = {}
score['r'] = P
score['s'] = R
score['p'] = S
T = input().strip()

i = 0
adptl = []
res = 0
while i < N:
    if i-K >= 0 and T[i-K] == T[i] and adptl[i-K] == 1:
        i += 1
        adptl.append(0)
        continue
    res += score[T[i]]
    adptl.append(1)
    i += 1

print(res)
# Original solution
N,K = list(map(int,input().split()))
R,S,P = list(map(int,input().split()))
D = {"r":P,"s":R,"p":S}
T = input().strip()
hist = [0 for _ in range(N)]
ans = 0
for i in range(N):
    a = T[i]
    if hist[i]==0:
        hist[i] = 1
        cnt = 1
        j = i
        while j+K<N and T[j+K]==a:
            hist[j+K]=1
            cnt += 1
            j += K
        ans += D[a]*(cnt-cnt//2)
print(ans)

# Optimized solution
N,K = list(map(int,input().split()))
R,S,P = list(map(int,input().split()))
D={"r":P,"s":R,"p":S}
T = input().strip()
A = {i:[] for i in range(K)}
for i in range(N):
    A[i%K].append(T[i])
cnt = 0
for k in range(K):
    if len(A[k])>0:
        cnt += D[A[k][0]]
        for i in range(1,len(A[k])):
            if A[k][i]==A[k][i-1]:
                A[k][i] = 0
            elif A[k][i]!=A[k][i-1]:
                cnt += D[A[k][i]]
print(cnt)
# Original solution
import sys
input = sys.stdin.readline


N, K = list(map(int, input().split()))
R, S, P = list(map(int, input().split()))
T = input().rstrip()

dp = [[0, 0, 0] for _ in range(N)]

for i in range(K):
    Q = T[i]
    if Q == "s":
        dp[i][0] = R
    elif Q == "p":
        dp[i][1] = S
    else:
        dp[i][2] = P

for i in range(K, N):
    Q = T[i]
    if Q == "s":
        dp[i][0] = max(dp[i-K][1], dp[i-K][2]) + R
        dp[i][1] = max(dp[i-K][0], dp[i-K][2])
        dp[i][2] = max(dp[i-K][0], dp[i-K][1])
    elif Q == "p":
        dp[i][0] = max(dp[i-K][1], dp[i-K][2])
        dp[i][1] = max(dp[i-K][0], dp[i-K][2]) + S
        dp[i][2] = max(dp[i-K][0], dp[i-K][1])
    else:
        dp[i][0] = max(dp[i-K][1], dp[i-K][2])
        dp[i][1] = max(dp[i-K][0], dp[i-K][2])
        dp[i][2] = max(dp[i-K][0], dp[i-K][1]) + P

ans = 0
for i in range(K):
    ans += max(dp[-1-i])
print(ans)

# Optimized solution
import sys
input = sys.stdin.readline



def main():
    N, K = list(map(int, input().split()))
    R, S, P = list(map(int, input().split()))
    T = list(input().rstrip())

    D = [[] for _ in range(K)]
    for i, t in enumerate(T):
        D[i%K].append(t)

    ans = 0
    for List in D:
        pre = -1
        for i, p in enumerate(List):
            if p == "r":
                s = P
            elif p == "s":
                s = R
            else:
                s = S
            if pre != p:
                ans += s
                pre = p
            else:
                pre = -1
    print(ans)
            

if __name__ == "__main__":
    main()
# Original solution
import sys
from collections import defaultdict
sys.setrecursionlimit(10**8)

n, k = list(map(int, input().split()))
r, s, p = list(map(int, input().split()))
t = list(map(str, input().rstrip()))

cir = defaultdict(list)
for i in range(k):
    cir[i] = t[i::k]


def solve(li, r, s, p):
    v = []

    def f(li, v):
        if len(li) == 0:
            return 0

        score = 0

        # グーを出す時
        if "r" not in v:
            x = "r"
            if li[0] == "s":
                score = max(score, f(li[1:], ["r"]) + r)
            else:
                score = max(score, f(li[1:], ["r"]))

        # チョキを出す時
        if "s" not in v:
            x = "s"
            if li[0] == "p":
                score = max(score, f(li[1:], ["s"]) + s)
            else:
                score = max(score, f(li[1:], ["s"]))

        # パーを出す時
        if "p" not in v:
            x = "p"
            if li[0] == "r":
                score = max(score, f(li[1:], ["p"]) + p)
            else:
                score = max(score, f(li[1:], ["p"]))

        return score
    return f(li, v)


ans = []
for i in range(k):
    ans.append(solve(cir[i], r, s, p))

print((sum(ans)))

# Optimized solution
from collections import defaultdict

n, k = list(map(int, input().split()))
r, s, p = list(map(int, input().split()))
t = list(map(str, input().rstrip()))

cir = defaultdict(list)
for i in range(k):
    cir[i] = t[i::k]


def solve(sq):
    # 初手
    x = sq[0]
    if x == "r":
        before, score = "r", p
    elif x == "s":
        before, score = "s", r
    else:
        before, score = "p", s
    cnt = 1

    # 前回と違う手なら問答無用で勝てる、前回と同じ手なら奇数回目に勝てる
    for x in sq[1:]:
        if before != x:
            if x == "r":
                score += p
            elif x == "s":
                score += r
            else:
                score += s
            before = x
            cnt = 1
        elif cnt % 2 == 1:
            cnt += 1
        else:
            if x == "r":
                score += p
            elif x == "s":
                score += r
            else:
                score += s
            cnt += 1
    return score


ans = []
for i in range(k):
    ans.append(solve(cir[i]))

print((sum(ans)))