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

from operator import itemgetter
import sys


def read():
    return sys.stdin.readline().rstrip()


def add(arr, i, x):
    while i < len(arr):
        arr[i] += x
        i += i & -i


def range_sum(arr, a, b):
    s = 0
    i = b
    while i > 0:
        s += arr[i]
        i -= i & -i
    i = a - 1
    while i > 0:
        s -= arr[i]
        i -= i & -i
    return s


def main():
    n, q = map(int, read().split())
    c = [int(i) for i in read().split()]
    queries = [() for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries.sort(key=itemgetter(2))
    last = [0] * n
    bit = [0] * (n + 1)
    ans = [-1] * q
    cr = 0
    for i, l, r in queries:
        for ri in range(cr, r):
            ci = c[ri] - 1
            if last[ci] > 0:
                add(bit, last[ci], -1)
            last[ci] = ri + 1
            add(bit, ri + 1, 1)
            cr = ri + 1
        ans[i] = range_sum(bit, l, r)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()


### FIXED CODE ###

from operator import itemgetter
import sys


class BIT:
    def __init__(self, size: int):
        self.size = size + 1
        self.array = [0] * self.size

    def add(self, i, x):
        if not i > 0:
            return
        while i < self.size:
            self.array[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.array[i]
            i -= i & -i
        return s


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, read().split())
    c = [int(i) for i in read().split()]
    queries = [() for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries.sort(key=itemgetter(2))
    last = [0] * n
    bit = BIT(n)
    ans = [-1] * q
    cr = 0
    for i, l, r in queries:
        for ri in range(cr, r):
            ci = c[ri] - 1
            bit.add(last[ci], -1)
            last[ci] = ri + 1
            bit.add(last[ci], 1)
            cr = ri
        ans[i] = bit.sum(r) - bit.sum(l - 1)
    print(*ans, sep="\n")


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

N,M = map(int,input().split(' '))
bridges = [ list(map(int,input().split(' '))) for _ in range(M) ]

output_list = [0]*(M+1)
unreach_bridge_len = N +1
base_num = N * (N-1) //2
output_list[M] = base_num
cluster_list = []

for i in reversed(range(M)):
    flag = True
    first_belongs = -1
    second_belongs = -1
    for idx,cluster in enumerate(cluster_list):
        if bridges[i][0] in cluster:
            first_belongs = idx
        if bridges[i][1] in cluster:
            second_belongs = idx
    if first_belongs == -1 and second_belongs == -1:
        cluster_list.append({bridges[i][0],bridges[i][1]})
    elif first_belongs == -1:
        cluster_list[second_belongs].add(bridges[i][0])
    elif second_belongs == -1:
        cluster_list[first_belongs].add(bridges[i][1])
    elif first_belongs != second_belongs:
        cluster_list[first_belongs] = cluster_list[first_belongs] | cluster_list[second_belongs]
        del cluster_list[second_belongs]
    current_amount = 0
    for cluster in cluster_list:
        current_amount += len(cluster) * (len(cluster) -1) //2
    output_list[i] = base_num - current_amount

for i in range(1,M+1):
    print(output_list[i])

### FIXED CODE ###

class UnionFind():
    '''
    @properties
        parents:
            - 各要素の親要素の番号を格納するリスト
            - 要素が根の場合はそのグループの要素数を格納する
    '''
    def __init__(self,n):
        self.n = n 
        self.parents = [-1] * n

    def __str__(self):
        return '\n'.join('{}: {}'.format(r,self.members(r)) for r in self.roots())
    
    def find(self,x):
        if self.parents[x] < 0: #初期値の場合
            return x
        else:
            self.parents[x] = self.find(self.parents[x]) #どの根に紐づいているかを判断する
            return self.parents[x]

    def union(self,x,y):

        x = self.find(x) #どの根に紐づいているかを判断する
        y = self.find(y) #どの根に紐づいているかを判断する

        if x == y: #同じ根に紐づいている場合は何もしない
            return
        
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        
        self.parents[x] += self.parents[y] #根の個数を増やす。。？
        self.parents[y] = x #根を変更する

    def members(self,x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0 ]
    
    def weighted_roots_sizes(self):
        return [ self.size(i) for i,x in enumerate(self.parents) if x < -1 ]
    
    def size(self,x):
        return -self.parents[self.find(x)]

N,M = map(int,input().split(' '))
bridges = [ list(map(int,input().split(' '))) for _ in range(M) ]
uf = UnionFind(N)
base_num = N * (N-1) //2
output_list = [0]*(M+1)
output_list[M] = base_num

for i in reversed(range(M)):
    bridge_from = bridges[i][0] - 1
    bridge_to = bridges[i][1] - 1
    current_amount = 0
    if uf.find(bridge_from) == uf.find(bridge_to):
        output_list[i] = output_list[i+1]
        continue
    output_list[i] = output_list[i+1] - uf.size(bridge_from) * uf.size(bridge_to)
    uf.union(bridge_from,bridge_to)

for i in range(1,M+1):
    print(output_list[i])
### BUGGY CODE ###

from collections import defaultdict

S = input()
B = defaultdict(int)
B[0]=1

for i in range(len(S)):
    B[int(S[-i-1:])%2019]+=1

ans=0

for j in B:
    ans+=(B[j]-1)*B[j]/2

print(int(ans))

### FIXED CODE ###

from collections import defaultdict

S = input()
B = defaultdict(int)
B[0]=1
ans=0
prev=0

for i in range(len(S)):
    m=(prev+int(S[-i-1])*pow(10,i,2019))%2019
    ans+=B[m]
    B[m]+=1
    prev=m

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

import numpy as np

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

a= np.array(a)

def light(a_list):
    outcome= np.array([0]*n)
    for i in range(n):
        outcome[max(0,i-a_list[i]):min(n,i+a_list[i]+1)] += 1
    return outcome

for _ in range(min(41,k)):
    if sum(a) >= n*n:
        break
    a = light(a)

[print(aa,end=' ') for aa in a]

### FIXED CODE ###

import numpy as np
from numba import njit

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

@njit(cache=True)
def light(n,a_list):
    outcome= np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        outcome[max(0,i-a_list[i])] += 1
        outcome[min(n,i+a_list[i]+1)] -= 1
    outcome = np.cumsum(outcome)[:-1]
    return outcome

for _ in range(k):
    if min(a) == n:
        break
    a = light(n,a)

[print(aa,end=' ') for aa in a]
### BUGGY CODE ###

import sys


def get_solve():
    cache = [None] * precalc_limit
    cache[0] = [0] * (weight_limit + 1)
    _vvv = vvv
    _www = www
    _weight_limit = weight_limit

    def _f(u):
        """ u < precalc_limit """
        if cache[u] is not None:
            return cache[u]
        dp = _f(u >> 1).copy()
        v = _vvv[u]
        w = _www[u]
        for x in range(_weight_limit, w - 1, -1):
            nv = dp[x - w] + v
            if dp[x] < nv:
                dp[x] = nv
        cache[u] = dp
        return dp

    return _f


n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)

solve = get_solve()

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        dp = solve(u)
        buf.append(dp[l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    dp = solve(u)
    for w, v in zip(dp_w, dp_v):
        nv = v + dp[l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
edge_l = []
edge_r = []
edge_c = []
for _ in range(m):
  l, r, c = map(int, input().split())
  edge_l.append(l - 1)
  edge_r.append(r - 1)
  edge_c.append(c)
l = np.array(edge_l, dtype=np.int)
r = np.array(edge_r, dtype=np.int)
c = np.array(edge_c, dtype=np.int)

dp = np.ones(n, dtype=np.int) * (c.sum() + 1)
dp[0] = 0
flag = True
for i in range(1, n):
  use = (l < i) * (r >= i)
  if np.all(~use):
    flag = False
    break
  dp[i] = np.min(dp[l[use]] + c[use])
  
if flag:
  print(dp[-1])
else:
  print(-1)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
edge = [[]] + [[(0, i)] for i in range(n-1)]
for _ in range(m):
  l, r, c = map(int, input().split())
  edge[l-1].append((c, r-1))

inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue and not check[-1]:
  dist, act = heapq.heappop(queue)
  check[act] = True
  for cost, vertex in edge[act]:
    if check[vertex]:
      continue
    d = dist + cost
    if dp[vertex] > d:
      heapq.heappush(queue, (d, vertex))
      dp[vertex] = d
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)
### BUGGY CODE ###

from heapq import heappush, heappop
import numpy as np
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [input() for _ in range(H)]


move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[-1] * W for _ in range(H)]


def bfs(i, j, d):
    visited[i][j] = d
    que = deque([(i, j, d)])

    while que:
        ci, cj, d = que.popleft()

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] != -1:
                continue
            if S[ni][nj] == '.':
                visited[ni][nj] = d
                que.append((ni, nj, d))


d = 0
for i in range(H):
    for j in range(W):
        if visited[i][j] == -1 and S[i][j] == '.':
            visited[i][j] = d
            bfs(i, j, d)
            d += 1

# print(visited)

G = [[] for _ in range(d+1)]
for ci in range(H):
    for cj in range(W):
        for di in range(-2, 3):
            for dj in range(-2, 3):
                ni, nj = ci+di, cj+dj
                if not (0 <= ni < H and 0 <= nj < W)  \
                        or visited[ci][cj] == -1 or visited[ni][nj] == -1:
                    continue
                if visited[ci][cj] != visited[ni][nj]:
                    u = visited[ci][cj]
                    v = visited[ni][nj]
                    G[u].append(v)
                    G[v].append(u)
startd = visited[Ch-1][Cw-1]
goald = visited[Dh-1][Dw-1]


def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * 10**7
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heappop(q)
        if dist[v] < d:
            continue
        for w in G[v]:
            d1 = d+1
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1, w))
    return dist


d1 = np.array(dijkstra(startd))
# print(d1)
if d1[goald] == 10**15:
    print(-1)
else:
    print(d1[goald])


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(input()) for _ in range(H)]

visited = [[-1] * W for _ in range(H)]

que = deque([(Ch-1, Cw-1, 0)])
move = ((1, 0), (-1, 0), (0, 1), (0, -1))
while que:
    ci, cj, d = que.popleft()

    if visited[ci][cj] != -1:
        continue
    visited[ci][cj] = d

    for di, dj in move:
        ni, nj = ci + di, cj + dj
        if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj] != -1:
            continue
        if S[ni][nj] == '.':
            que.appendleft((ni, nj, d))

    for di in range(-2, 3):
        for dj in range(-2, 3):
            ni, nj = ci+di, cj+dj
            if not (0 <= ni < H and 0 <= nj < W)  \
                    or visited[ni][nj] != -1:
                continue
            if S[ni][nj] == '.':
                que.append((ni, nj, d+1))
    # print(visited)
    # exit()

if visited[Dh-1][Dw-1] == -1:
    print(-1)
else:
    print(visited[Dh-1][Dw-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
from collections import deque
ans=10**9
f=1
g=3
for i in range(2,n-1):
    l=a[:i]
    r=a[i:]
    k1=deque(a[:f])
    k2=deque(a[f:i])
    k3=deque(a[i:g])
    k4=deque(a[g:])
    while len(k2) > 1 and abs(sum(k1)-sum(k2)) > abs((sum(k1)+k2[0])-(sum(k2)-k2[0])):
        k1.append(k2.popleft())
        f+=1
    while len(k4) > 1 and abs(sum(k3)-sum(k4)) > abs((sum(k3)+k4[0])-(sum(k4)-k4[0])):
        k3.append(k4.popleft())
        g+=1
    ans=min(ans,max(abs(sum(k1)-sum(k2)),abs(sum(k1)-sum(k3)),abs(sum(k1)-sum(k4))
                ,abs(sum(k2)-sum(k3)),abs(sum(k2)-sum(k4)),abs(sum(k3)-sum(k4))))
print(ans)

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
a=[0]
c=0
for si in s:
    c+=si
    a.append(c)
ans=[]
f=1
g=3
for i in range(2,n-1):
    while abs(a[f]-(a[i]-a[f])) > abs(a[f+1]-(a[i]-a[f+1])):
        f+=1
    while abs(a[g]-a[i]-(a[n]-a[g])) > abs(a[g+1]-a[i]-(a[n]-a[g+1])):
        g+=1
    ls=[a[f],a[i]-a[f],a[g]-a[i],a[n]-a[g]]
    ans.append(max(ls)-min(ls))
print(min(ans))
### BUGGY CODE ###

s = input()
t = input()
#dp 0で初期化
#dp[i+1][j+1] sのi文字目までとtのj文字目までの最長部分列の長さ
#もしs[i] == t[j]なら、dp[i][j]に対して1文字増やせる => dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1) ...わかる
#dp[i+1][j+1] = max(dp[i+1][j],dp[i+1][j+1])　　...？
#dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j+1])　　...？
#dp[i+1][j+1]
dp = [[0]*(len(t)+1) for i in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])

#復元
i = len(s)
j = len(t)
res = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        res = s[i-1] + res
        i -= 1
        j -= 1
print(res)


### FIXED CODE ###

s = input()
t = input()
#dp 0で初期化
#dp[i+1][j+1] sのi文字目までとtのj文字目までの最長部分列の長さ
#もしs[i] == t[j]なら、dp[i][j]に対して1文字増やせる => dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1) ...わかる
#dp[i+1][j+1] = max(dp[i+1][j],dp[i+1][j+1])　　...？
#dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j+1])　　...？
#dp[i+1][j+1]
dp = [[0]*(len(t)+1) for i in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1])

#復元
i = len(s)
j = len(t)
res = ""
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        res = s[i-1] + res
        i -= 1
        j -= 1
print(res)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque
import sys
sys.setrecursionlimit(700000)

NIL = -1
N, M, K = map(int, input().split())
friends = [deque() for i in range(N)]
block = [deque() for i in range(N)]
prefriends = [deque() for i in range(N)]

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

for i in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    block[C].append(D)
    block[D].append(C)


def dfs(x, y):
    for i in friends[y]:
        if check[i]:
            #print(i)
            prefriends[x].append(i)
            #print(set(prefriends[x]))
            check[i] = False
            dfs(x, i)
ans = [0]*N
#print(prefriends)
for j in range(N):
    #print(prefriends[j])
    check = [True]*N
    check[j] = False
    dfs(j, j)
    #print(set(prefriends[j]))
    #print(set(friends[j]))
    #print(set(block[j]))
    #print((set(prefriends[j]) - set(friends[j])) - set(block[j]))
    
    ans[j] = (set(prefriends[j]) - set(friends[j])) - set(block[j])
    #print(ans[j])
    #print()
ans = [len(ans[i]) for i in range(N)]
print(*ans)



### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque
import sys
sys.setrecursionlimit(700000)

NIL = -1
N, M, K = map(int, input().split())
relation = [deque() for i in range(N)]
prefriends = [deque() for i in range(N)]

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

def dfs(x, y):
    for i in relation[y]:
        if check[i] == None:
            #print(i)
            prefriends[x].append(i)
            #print(set(prefriends[x]))
            check[i] = x
            dfs(x, i)

#print(prefriends)
j = 0
check = [None]*N
while j < N:
    if check[j] == None:
        #print(prefriends[j])
        prefriends[j].append(j)
        check[j] = j
        dfs(j, j)
        #print(check)
    j += 1
    #print(set(prefriends[j]))
    #print(set(friends[j]))
    #print(set(block[j]))
    #print((set(prefriends[j]) - set(friends[j])) - set(block[j]))

for i in range(K):
    C, D = map(int, input().split())
    C -= 1
    D -= 1
    if check[C] == check[D]:
        relation[C].append(D)
        relation[D].append(C)
ans = [0]*N
for j in range(N):
    ans[j] = len(prefriends[check[j]]) - len(relation[j]) - 1
    #print(ans[j])
    #print()
print(*ans)
### BUGGY CODE ###

n = int(input())
*a, = map(int, input().split())
dp = [False] * n

for i in range(n):
    for j in range(n):
        if (i != j) and (a[i] % a[j] == 0):
            break
    else:
        dp[i] = True

print(dp.count(True))

### FIXED CODE ###

n = int(input())
*a, = sorted(map(int, input().split()))
a_max = a[n-1]
dp = [True] * a_max
ans = 0
recent = 0

if n == 1:
    print(1)
    exit()

for i in a:
    if recent == i:
        ans -= 1
        recent = 0
    if dp[i-1] == False:
        continue
    else:
        for j in range(i, a_max+1, i):
            dp[j-1] = False
        ans += 1
        recent = i

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

a,b,n=map(int,input().split())
'''
lst=[]
for i in range(n+1):
    now=int(a*i/b)-a*int(i/b)
    lst.append(now)
print(max(lst))
'''
lst=[]
if n>=b:
    ans=int(a*(n-1)/b)-a*int((n-1)/b)
    ans2=int(a*n/b)-a*int(n/b)
    for i in range(n//b+1):
        ans3=int(a*(i*b-1)/b)-a*int((i*b-1)/b)
        lst.append(ans3)
    print(max(ans,ans2,max(lst)))

else:
    ans=int(a*(n)/b)-a*int((n)/b)
    print(max(ans,0))

### FIXED CODE ###

a,b,n=map(int,input().split())
def ans(x):
    return int(a*x/b)
print(ans(min(n,b-1)))
### BUGGY CODE ###

n, m = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(m)]
b = [x[1] for x in l if x[0]==1]
a = [x[0] for x in l if x[1]==n]
for i in b:
    if i in a:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
l = [tuple(map(int, input().split())) for i in range(m)]
c = [[] for _ in range(n+1)]
for x in l:
    c[x[0]].append(x[1])
    c[x[1]].append(x[0])
if set(c[1])&set(c[n]):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import numpy as np
def f(n):
    count = 0
    x_max = int(np.sqrt(n/6)//1)
    for x in range(1,x_max+1):
        y_max = int(np.sqrt((n-x**2-2*x)/3)//1)
        for y in range(x,y_max+1):
            z_max = int(np.sqrt(n-x**2-y**2-x*y-x-y)//1)
            for z in range(y,z_max+1):
                if x**2+y**2+z**2+x*y+y*z+z*x == n:
                    if x==y and y==z:
                        count += 1
                    elif x==y and y<z:
                        count += 3
                    elif x<y and y==z:
                        count += 3
                    elif x<y and y<z:
                        count += 6

    return count

N = int(input())
if N >=6:
    for i in range(5):
        print(0)
    for i in range(5,N):
        print(f(i+1))
else:
    for i in range(N):
        print(0)

### FIXED CODE ###

import numpy as np
def f(n):
    counts = [0]*n
    x_max = int(np.sqrt(n))
    for x in range(1,x_max+1):
        y_max = int(np.sqrt(n-x**2))
        for y in range(1,y_max+1):
            z_max = int(np.sqrt(n-x**2-y**2))
            for z in range(1,z_max+1):
                if x**2+y**2+z**2+x*y+y*z+z*x <= n:
                    counts[x**2+y**2+z**2+x*y+y*z+z*x-1] += 1
    return counts
 
N = int(input())
counts = f(N)
for i in range(N):
    print(counts[i])
### BUGGY CODE ###

import re
X = raw_input()
iter = 100000
pat = re.compile('(ST)')
for i in xrange(iter):
    X =	X.replace('ST','')
    if len(X) == 0:
        break
print len(X)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    x = S()
    s_cnt = 0
    removed = 0
    for c in x:
        if c == 'S':
            s_cnt += 1
        if c == 'T':
            if s_cnt > 0:
                s_cnt -= 1
                removed += 2
    print(len(x) - removed)
main()
### BUGGY CODE ###

n = int(input())
p = input().split()
p = [int(i) for i in p]

c = 0
for i in range(n):
    for j in range(i):
        if p[i] <= p[j]:
            continue
        else:
            break
    else:
        c += 1

print(c)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

'''
選んだ数字(iで場所指定)より、左の数字が全て大きい。
'''
c = 0
MIN = p[0]
for i in range(n):
    if p[i] <= MIN:
        c += 1
        MIN = p[i]

print(c)