Harryxun/stf_run huggingface dataset:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

def popcount(i):
    return bin(i).count('1')

N = INT()
S = list(input())
X = int(''.join(S), 2)
S = S[::-1]
base = S.count('1')

for i in range(N-1, -1, -1):
    cur = X ^ (1<<i)
    cnt = 1
    if S[i] == '1':
        cur %= base - 1
    else:
        cur %= base + 1
    while cur:
        cur %= popcount(cur)
        cnt += 1
    print(cnt)


### FIXED CODE ###

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

def popcount(i):
    return bin(i).count('1')

N = INT()
S = list(map(int, input()))[::-1]

pcnt1 = S.count(1) - 1
pcnt2 = S.count(1) + 1
base1 = base2 = 0
for i in range(N):
    if S[i]:
        if pcnt1 != 0:
            base1 += pow(2, i, pcnt1)
        base2 += pow(2, i, pcnt2)

ans = [0] * N
for i in range(N):
    if S[i] and pcnt1 == 0:
        ans[i] = 0
        continue
    cur = 0
    if S[i]:
        cur += (base1 - pow(2, i, pcnt1)) % pcnt1
    else:
        cur += (base2 + pow(2, i, pcnt2)) % pcnt2
    cnt = 1
    while cur:
        cur %= popcount(cur)
        cnt += 1
    ans[i] = cnt
for a in ans[::-1]:
    print(a)
input_line=input().rstrip().split(" ")
a=int(input_line[0])
b=int(input_line[1])
c=int(input_line[2])
if a==b==5 or a==c==5 or b==C==5:
    if a+b+c==17:
        print("YES")
elif a+b+c!=17:
    print("NO")


### FIXED CODE ###

input_line=input().rstrip().split(" ")
five=int(input_line.count("5"))
seven=int(input_line.count("7"))
if five==2 and seven==1:
    print("YES")
else:
    print("NO")
s = input()
t = input()
dp = [[0]*(len(t)+1) for i in range(len(s)+1)]
#dp[i+1][j+1]sのi文字目までとtのj文字目までを比較したときのLCS
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

i = len(s)
j = len(t)
ans = ''
while (i>=0 and j >= 0):
    if(dp[i+1][j] > dp[i][j+1] ):i-=1
    elif (dp[i+1][j] < dp[i][j+1]):j -= 1
    else:ans = s[i]+ ans
print(ans)


### FIXED CODE ###

s = input()
t = input()
dp = [[0]*(len(t)+1) for i in range(len(s)+1)]
#dp[i+1][j+1]sのi文字目までとtのj文字目までを比較したときのLCS
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

i = len(s)-1
j = len(t)-1
ans = ''
while j>= 0 and i >= 0:
    if dp[i][j+1] == dp[i+1][j+1]:i-= 1
    elif dp[i+1][j] == dp[i+1][j+1] :j-= 1
    else:
        ans = s[i] + ans
        i -= 1
        j -= 1
        
print(ans)
n = int(input())
h = list(map(int, input().split()))

sa = []

for i in range(n-1):
    sa.append(h[i+1]-h[i])

#print(sa)

ans = 0
for i in range(n-1):
    if sa[i] == 0 and sa[i+1] == -1:
        print('No')
        exit(0)
    else:
        if sa[i] < 0:
            ans += 1
    
    if ans > 1:
        print('No')
        exit(0)
        
#print(ans)
print('Yes')

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
f=True
m=0
for i in range(n):
    if h[i]>m:
        m=h[i]-1
    elif h[i]==m:
        continue
    else:
        f=False
        break
print('Yes' if f else 'No')
N = input()
A = sorted(map(int, input().split()), reverse=True)

p = [x for x, y in zip(A[:-1], A[1:]) if x == y]
print(p[0] * p[1])


### FIXED CODE ###

N = int(input())

ans = 1
cnt = 2
w = 0
for Ai in sorted(map(int, input().split()), reverse=True):
  if w != Ai:
    w = Ai
  else:
    ans *= w
    cnt -= 1
    if cnt <= 0:
      break
    w = 0

print(ans if cnt <= 0 else 0)
n, m = [int(x) for x in input().split(' ')]
a = set(int(input()) for x in range(m))

m = [0] * n
m[0] = 1 if 1 not in a else 0
m[1] = 2 if 2 not in a else 0

if m[0] == 0 and m[1] == 2:
    m[1] = 1

for i in range(2, n):
    if i+1 not in a:
        m[i] = m[i-1] + m[i-2]

print(m[-1] % 1000000007)


### FIXED CODE ###

n, m = [int(x) for x in input().split(' ')]
a = set(int(input()) for x in range(m))

m = [0] * n
m[0] = 1 if 1 not in a else 0

if n == 1:
    print(m[0])
    exit()

m[1] = 2 if 2 not in a else 0

if m[0] == 0 and m[1] == 2:
    m[1] = 1

for i in range(2, n):
    if i+1 not in a:
        m[i] = m[i-1] + m[i-2]

print(m[-1] % 1000000007)
n = int(input())
a = sorted(map(int, input().split()), reverse=True)

ans, que = 0, [a[0]]
for i in enumerate(a[1:]):
    ans += que[i]
    que += [i, i]
print(ans)


### FIXED CODE ###

from collections import deque

n = int(input())
a = sorted(map(int, input().split()), reverse=True)

ans, cnt = 0, deque([a[0]])
for i in a[1:]:
    ans += cnt.popleft()
    cnt.append(i)
    cnt.append(i)
print(ans)
a, b, c = [int(x) for x in input()]
string = max([c - a - b,0])
print(string)

### FIXED CODE ###

a, b, c = [int(x) for x in input().split()]
water = max(c - (a - b), 0)
print(water)
import collections

def bfs(N):
    S = "abcdefghij"
    result = []
    deq = collections.deque(["a"])

    while deq:
        s = deq.popleft()
        if len(s) == N:
            result.append(s)
            continue
        else:
            for i in S[:len(set(s))+1]:
                deq.append(s + i)
    return result

N = int(input())
ans = bfs(N)
for a in ans:
    print(a)
exit()

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
Flag = True
for _ in range(Q):
    q = input().split()
    if len(q) == 1:
        Flag = False if Flag else True
    else:
        if Flag:
            if q[1] == '1':
                S.appendleft(q[2])
            else:
                S.append(q[2])
        else:
            if q[1] == '1':
                S.append(q[2])
            else:
                S.appendleft(q[2])

if Flag:
    print(''.join(S))
else:
    print(''.join(reversed(S)))
# import math これだとエラーになる 3.4なので
from fractions import gcd
a, b = map(int, input().split())

print(int((a*b)//gcd(a, b)))

### FIXED CODE ###

x = int(input())

ans = 0

for _ in range(10**5):
    if x == 2:
        print(x)
        break
    for i in range(2, int(x**0.5) + 1):
        if (x % i) == 0:
            break
        elif i == int(x**0.5): # ループの最後
            ans = x
        else:
            pass

    if ans != 0:
        print(ans)
        break
    else:
        x += 1
import numpy as np

n, m, x = map(int, input().split())
a = np.array(list(map(int, input().split())))


print(min(len(a[a<x]),len(a[a>x])))

### FIXED CODE ###

import numpy as np

n, m, x = map(int, input().split())
a = np.array(list(map(int, input().split())))


print(min(len(a[a<x]),len(a[a>x])))
X = int(input())
XX=np.arange(X,X+10**4)

s=0
for j in XX:
    if (s==1):
        break
    for i in range(2, j+1):
        N= j % i
#        print('j=' ,j ,' i=' ,i, N)
        if (N ==  0 and i==j ):
            print(j)
            s=1
        if (N ==  0):
          #  print('true')
            break
#        else:
#            print(j)


### FIXED CODE ###

import numpy as np
#import copy
#import fractions
#
###############入  力###################
#a, b, c, d = map(int, input().split())  # a=2 b=4 c=5 d =7
#a = list(map(int, input().split()))     # a = [2, 4, 5, 6]
#s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
##行数指定
##3
##hoge
##foo
##bar
#n=int(input())
#string_list=[input() for i in range(n)] #['hoge','foo','bar']
#
###############初期化、コピー##############
#a=[0]*5 #[0, 0, 0, 0, 0]
#b=copy.deepcopy(a)  #2次元配列はこうコピーする
#b2=a[:]  #1次元のときはコピーはこれで良い
#
###############小数点表示################
#a = 0.364364
#print(a) #0.364364
#print("{:.6f}".format(a)) #0.364364
#print("{:.4f}".format(a)) #0.3644 小数点第4位に丸めることもできる。
#
###############ゼロ埋め・幅寄せ################
#print("python".ljust(15,'-')) # 左詰め　　　 #python---------
#print("python".center(15,'-'))# 中央寄せ　　#-----python----
#print("python".rjust(15,'-')) # 右詰め　　　 #---------python
#print(str(29).rjust(10,'0')) #10桁ゼロ埋め　 #0000000029
#
###############文字列操作################
#'abc123def'[:] #すべての文字列が取れる #'abc123def'
#'abc123def'[-1:] #終端文字がとれる    #'f'
#'abc123def'[:-1] #最後の1文字以外のものがとれる。 #'abc123de'
#'abc123def'[::-1] #文字が逆転する #'fed321cba'
#
###############二分探索################
#import bisect
#listA=[1,2,5,2,4,6,7,8,6,56,3,56,76,34,32,2,6,0,32,6,0] 
#listA.sort()
#zeroindex=bisect.bisect_right(listA,0) #ソートされたリスト内で0の場所を探し、右側Indexを返す
#clearlistA=listA[zeroindex:]#0以下が存在しないリストを得る
#
#
###############最小公倍数,最大公約数
#import fractions
#a,b=map(int, input().split())
#a,b= 24, 6
#f=fractions.gcd(a,b)
#f2=a*b//f
#print(f,f2)
#
###############四則演算
#a + b #足し算（加算）: +演算子
#a - b#引き算（減算）: -演算子
#a * b#掛け算（乗算）: *演算子
#a / b#割り算（除算）: /演算子
#a// b#割り算の整数部（整数除算）: //演算子
#a % b#割り算の剰余（余り, mod）: %演算子
#a** b#べき乗: **演算子

X = int(input())
XX=np.arange(X,X+10**4)

s=0
for j in XX:
    if (s==1):
        break
    for i in range(2, j+1):
        N= j % i
#        print('j=' ,j ,' i=' ,i, N)
        if (N ==  0 and i==j ):
            print(j)
            s=1
        if (N ==  0):
          #  print('true')
            break
#        else:
#            print(j)
n,m = map(int,input().split())
g = 1
for i in range(m):
  if m%i == 0:
    if int(m/i) >= n:
      g = int(m/i)
    else:
      break
      
print(g)
  

### FIXED CODE ###

n,m = map(int,input().split())
g = 1
def fact(k):
  a = []
  for i in range(1,int(k **(0.5))+1):
    if k%i ==0:
      a.append(i)
      a.append(int(k/i))
  b = list(set(a))
  b.sort()
  return b

g = fact(m)
for i in range(len(g)):
  if g[len(g)-i-1] <= m/n:
    print(g[len(g)-i-1])
    break
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

for i in range(n-k):
  if t[i] == t[i+k]:
    t[i+k] = 0
print(sum(t.count("r")*r + t.count("s")*s + t.count("p")*p))

### FIXED CODE ###

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

for i in range(n-k):
  if t[i] == t[i+k]:
    t[i+k] = 0

print(sum([t.count("r")*p, t.count("s")*r, t.count("p")*s]))
import numpy as np
N=input()
A=map(int,input().split())
B=map(int,input().split())
C=array(map(int,input().split()))

sb=sum(B)
dC=np.diff(A)
sC=C[np.where(dC==1)[0]].sum()

print(sb+sC)


### FIXED CODE ###

import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=list(map(int,input().split()))
C=np.array(list(map(int,input().split())))

sb=sum(B)
dC=np.diff(A)

sC=C[A[np.where(dC==1)[0]]-1].sum()
#print(sb, sC)
print(sb+sC)
n = int(input())
li = list(map(int,input().split()))

dp = [[-1 for i in range(1000)] for j in range(1000)]
ans = [100000]*n
ans[0] = 0
def solve(a,b,dp,li):
    # print(f"{a,b}")
    if dp[a][b] !=-1 :
        # print(f"結果{dp[a][b]}")
        return dp[a][b]
    else:
        dp[a][b] = abs(li[a]-li[b])
        # print(f"結果{a,b,dp[a][b]}")
        return dp[a][b]

for i in range(2,n+1):
    # print(i)
    if i == 2:
        dp[1][0] = abs(li[1]-li[0])
        ans[i-1] = dp[1][0]
    else:
        # print(solve(i-1,i-2,dp,li)+ans[i-2],solve(i-1,i-3,dp,li)+ans[i-3])
        # print(solve(i-1,i-2,dp,li),solve(i-1,i-3,dp,li))
        # print(ans[i-2],ans[i-3])
        # print(li[i-1],li[i-3])
        ans[i-1] = min(solve(i-1,i-2,dp,li)+ans[i-2],solve(i-1,i-3,dp,li)+ans[i-3])

print(ans[-1])
# print(dp)


### FIXED CODE ###


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

# dp = [[-1 for i in range(1100)] for j in range(1100)]
ans = [0]*n
ans[0] = 0
# def solve(a,b,dp,li):
#     if dp[a][b] !=-1 :
#         return dp[a][b]
#     else:
#         dp[a][b] = abs(li[a]-li[b])
#         return dp[a][b]

for i in range(2,n+1):
    if i == 2:
        ans[i-1]= abs(li[1]-li[0])
    else:
        ans[i-1] = min(abs(li[i-1]-li[i-2])+ans[i-2],abs(li[i-1]-li[i-3])+ans[i-3])

print(ans[-1])
wt = str(input())
if wt == 'SSS':
    print(0)
if wt == "RRR":
    print(3)
else:
    id = wt.index('R')
    if wt.count('R') == 2 and wt[id] == wt[id+1] == 'R':
        print(2)
    else:
        print(1)

### FIXED CODE ###

wt = str(input())
if wt == 'SSS':
    print(0)
elif wt == "RRR":
    print(3)
else:
    id = wt.index('R')
    if wt.count('R') == 2 and wt[id] == wt[id+1] == 'R':
        print(2)
    else:
        print(1)
N, K = map(int,input().split())
A = [0] + list(map(int,input().split()))
T = [1]
current_town = 1
for i in range(2,K+1):
    current_town = A[current_town]
    K -= 1
    if current_town in T:
        loop_towns = T[T[current_town]-1:]
        print(loop_towns[K%len(loop_towns)])
        break
    else:
        T.append(current_town)
else:
    print(A[current_town])

### FIXED CODE ###

N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
T={}
T[1]=1
t=1
for i in range(2,K+1):
    a=A[t]
    t=a
    K-=1
    if a in T:
        l=list(T.keys())[T[a]-1:]
        print(l[K%len(l)])
        break
    else:
        T[a]=i
else:
    print(A[t])
from math import sqrt
x1, y1, x2, y2 = map(int, input().split())
r = sqrt((x2 - x1)**2 + (y2 - y1)**2)
print(r)

### FIXED CODE ###

import math
x1, y1, x2, y2 = map(float, input().split())
print(math.sqrt((x2 - x1)**2 + (y2 -y1)**2))
w=sorted(list(input()));s="Yes" 
for i in range(0,len(w),2):
    if w[i]!=w[i+1]:s="No"
print(s)

### FIXED CODE ###

w=sorted(list(input()))+["_"];s="Yes" 
for i in range(1,len(w),2):
    if w[i]!=w[i-1]:s="No"
print(s)
def func(x, graph, flag, dp):
    if (flag[x]):
        return dp[x]

    flag[x] = 1
    check = 0
    for i in graph[x]:
        check = max(check, func(i, graph, flag, dp) + 1)

    dp[x] = check

    return dp[x]

N, M = [int(i) for i in input().split()]
flag = [0] * (N + 1)
dp = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
#%%
for _ in range(M):
    temp_x, temp_y = [int(i) for i in input().split()]
    graph[temp_x].append(temp_y)

#%%
ans = 0
for i in range(1, N + 1):
    ans = max(ans, func(i, graph, flag, dp))

print(ans)


### FIXED CODE ###

#%%
from sys import stdin, setrecursionlimit as srl
from threading import stack_size
srl(int(1e9)+7)
stack_size(int(1e8))

def func(x, graph, flag, dp):
    if (flag[x]):
        return dp[x]

    flag[x] = 1
    check = 0
    for i in graph[x]:
        check = max(check, func(i, graph, flag, dp) + 1)

    dp[x] = check

    return dp[x]

N, M = [int(i) for i in input().split()]
flag = [0] * (N + 1)
dp = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
#%%
for _ in range(M):
    temp_x, temp_y = [int(i) for i in input().split()]
    graph[temp_x].append(temp_y)

#%%
ans = 0
for i in range(1, N + 1):
    ans = max(ans, func(i, graph, flag, dp))

print(ans)
N = int(input())
Ss = []
for i in range(N):
  Ss.append(int(input()))

C0, C1, C2, C3 = 0, 0, 0, 0
for S in Ss:
  if S == 'AC':
    C0 += 1
  elif S == 'WA':
    C1 += 1
  elif S == 'TLE':
    C2 += 1
  else:
    C3 += 1
print("AC X {}".format(C0))
print("WA X {}".format(C1))
print("TLE X {}".format(C2))
print("RE X {}".format(C3))

### FIXED CODE ###

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

for j in ["AC", "WA", "TLE", "RE"]:
  print("{} x {}".format(j, Ss.count(j)))
n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from math import gcd
ans = a[0]
for i in range(1, n):
    ans = ans*a[i]//gcd(ans, a[i])
# s = sum(pow(x, mod-2, mod) for x in a)
s = sum((1/x)%mod for x in a)
print(int(s*ans%mod))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from math import gcd
cm = 1
for i in range(n):
    cm = cm*a[i]//gcd(cm, a[i])
ai = sum(pow(x, mod-2, mod) for x in a)
print(int(ai*cm%mod))
x_1,y_1,x_2,y_2=tuple(map(int,input().split()))

be=[x_2-x_1,y_2-y_1]
za3=[x_2+(-1)*be[1],y_2+be[0]]
za4=[x_1+(-1)*be[1],y_1+be[0]]

print(za3[0],za3[1],za4[0],za4[1])

### FIXED CODE ###

n=int(input())
if n % 2==0:
	print((n//2)**2)
else:
	m=(n+1)//2
	print(m*(n-m))
import bisect, functools
N = int(input())
A = sorted(int(x) for x in input().split())
B = sorted(int(x) for x in input().split())
C = sorted(int(x) for x in input().split())

@functools.lru_cache(maxsize=None)
def a(n):
    return bisect.bisect_left(A, n)

@functools.lru_cache(maxsize=None)
def b_i(i):
    if i >= 1:
        return b_i(i - 1) + a(B[i - 1])
    return 0

@functools.lru_cache(maxsize=None)
def b(n):
    return b_i(min(len(B), bisect.bisect_left(B, n)))

def c():
    return sum(b(x) for x in C)

print(c())

### FIXED CODE ###

K = int(input())

import heapq
def dijkstra(adj, n, start):
    dj = [10**6] * (n + 1)
    dj[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        fc, fn = heapq.heappop(q)
        if dj[fn] < fc: continue
        for tn, lc in adj[fn]:
            if dj[tn] > dj[fn] + lc:
                dj[tn] = dj[fn] + lc
                heapq.heappush(q, (dj[tn], tn))
    return dj

adj = {}
for i in range(K):
    t = adj.setdefault(i, [])
    t.append(((i + 1) % K, 1))
    t.append(((i * 10) % K, 0))

costs = dijkstra(adj, K - 1, 1)
print(costs[0] + 1)
import numpy as np
n = int(input())
a_ls = list(map(int, input().split()))
csum = list(np.cumsum(a_ls))
ans = 0

for start in range(1,n):
    for end in range(start, n):
        if csum[end] - csum[start-1] == 0:
            ans += 1
for i in range(n):
    if csum[i] == 0:
        ans += 1
print(ans)



### FIXED CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
a_ls = list(map(int, input().split()))
a_csum = [0] * n
now = 0
for i in range(n):
    now += a_ls[i]
    a_csum[i] = now
a_csum.append(0)
a_csum.sort()
ans = 0
now = 0
for i in range(n):
    if a_csum[i] == a_csum[i+1]:
        now += 1
    else:
        if now > 0:
            ans += combinations_count(now+1,2)
        now = 0
if now > 0:
    ans += combinations_count(now+1,2)
print(ans)
K = int(input())
if K % 2 == 0 or K % 5 == 0: print(-1)
else:
  count = 1
  while True:
    num = 7 / 9 * (10 ** count - 1)
    if num % K == 0:
      print(count)
      break
    count += 1


### FIXED CODE ###

K = int(input())
x = 7 % K
num_list = []

for count in range(1, K + 1):
  if x == 0:
    print(count)
    break
  x = (x * 10 + 7) % K

else: print(-1)
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()

def main():
    X = ii()
    print(360//math.gcd(X,360))

if __name__ == "__main__":
  main()


### FIXED CODE ###

import math
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()

def main():
    X = ii()
    print(360//math.gcd(X,360))

if __name__ == "__main__":
  main()
N,Q=map(int,input().split())
S=input()
l,r=[map(int,input().split()) for i in range(Q)]
for j in range(Q):
  print(S.count("AC",l[j],r[j]+1))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t=[0]*(N+1)
for i in range(N):
  t[i+1]=t[i]+(1 if S[i:i+2]=="AC" else 0)
for i in range(Q):
  l,r=map(int,input().split())
  print(t[r-1]-t[l-1])
input_num = int(input())
nums = input().split()
ope_cnt = 0
def division_nums(input_num, nums, ope_cnt):
  for i in range(input_num):
    if int(nums[i]) % 2 != 0:
      return ope_cnt
    else:
      nums[i] = int(nums[i]) / 2
  ope_cnt = ope_cnt + 1
  return division_nums(input_num, nums, ope_cnt)
      
print(divisiton_nums(input_num, nums, ope_cnt))

### FIXED CODE ###

input_num = int(input())
nums = input().split()
ope_cnt = 0
def division_nums(input_num, nums, ope_cnt):
  for i in range(input_num):
    if int(nums[i]) % 2 != 0:
      return ope_cnt
    else:
      nums[i] = int(nums[i]) / 2
  ope_cnt = ope_cnt + 1
  return division_nums(input_num, nums, ope_cnt)
      
print(division_nums(input_num, nums, ope_cnt))
import math

a, b, c = map(float, raw_input())

print a*b*math.sin(c)/2
print a+b+math.sqrt(a**2+b**2-2*a*b*math.cos(c))
print b*math.sin(c)

### FIXED CODE ###

import math

a, b, c = map(float, raw_input().split())
c = c/180*math.pi

print a*b*math.sin(c)/2
print a+b+math.sqrt(a**2+b**2-2*a*b*math.cos(c))
print b*math.sin(c)
S = str(input())
if S = 'ABC':
  print('ARC')
else:
  print('ABC')

### FIXED CODE ###

S = str(input())
if S == 'ABC':
    print('ARC')
else:
    print('ABC')
A = input()
l = A.split(,)
print(l[0],' ',l[1],' ',l[2],' ')

### FIXED CODE ###

A = input()
l = A.split(',')
print(l[0],' ',l[1],' ',l[2],' ')
import sys
input = sys.stdin.readline
 
#input
N = int(input())
A = list(map(int, input().split()))
 
from collections import Counter
import numpy as np
 
l = Counter(A).most_common()
l = [b for a, b in l]
l = np.array(l)
 
maximum_operation = [0] * N
for K in range(len(l)):
    l = Counter(A).most_common()
    l = [b for a, b in l]
    l = np.array(l)
    while l[K] > 0:
        l[0:K+1] -= 1
        l = np.sort(l, kind = "quicksort")[::-1]
        maximum_operation[K] += 1
 
for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * N
    for i, a in enumerate(A):
        idxs[a] = i
    def func(arr):
        if len(arr) == 0:
            return 0
        a = min(arr)
        idx = idx[a]
        return (idx + 1) * (len(arr) - idx) * a + func(arr[:idx]) + func(arr[idx + 1:])
    ans = func(A)

    return ans

print(main())


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A):
        idxs[a] = i
    ll = list(range(N + 1))
    rr = list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        idx = idxs[a]
        l, r = ll[idx], rr[idx]
        ans += (idx - l + 1) * (r - idx + 1) * a
        ll[r + 1] = l
        rr[l - 1] = r

    return ans

print(main())