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

import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

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

antena=[]
for i in range(N):
    if len(edge[i])>2:
        antena.append(i)

if not antena:
    print(1)
    exit()

parent=[-1]*N
root=antena[0]

def dfs(v,pv):
    parent[v]=pv
    for i in edge[v]:
        if i!=pv:
            dfs(i,v)

dfs(root,-1)

antena=set(antena)

q=[root]
sub=[]
while q:
    while q:
        x=q.pop()
        if x in antena:
            v=x
            while parent[v] not in antena and parent[v]!=-1:
                antena.add(parent[v])
                v=parent[v]
        for nv in edge[x]:
            if nv!=parent[x]:
                sub.append(nv)

        if not q:
            q=sub
            sub=[]
            break

ans=0
for u in antena:
    if len(edge[u])==1:
        ans+=1
    elif len(edge[u])==2:
        check=0
        for v in edge[u]:
            check+=(v in antena)
        if check==1:
            ans+=1
    else:
        check=0
        for v in edge[u]:
            check+=(v in antena)
        if check>=len(edge[u])-1:
            continue
        else:
            ans+=len(edge[u])-1-check
print(ans)


### FIXED CODE ###

import sys

input=sys.stdin.readline
sys.setrecursionlimit(10**7)

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

antena=[]
for i in range(N):
    if len(edge[i])>2:
        antena.append(i)

if not antena:
    print(1)
    exit()

parent=[-1]*N
root=antena[0]

def dfs(v,pv):
    parent[v]=pv
    for i in edge[v]:
        if i!=pv:
            dfs(i,v)

dfs(root,-1)

antena=set(antena)

q=[root]
sub=[]
while q:
    while q:
        x=q.pop()
        if x in antena:
            v=x
            while parent[v] not in antena and parent[v]!=-1:
                antena.add(parent[v])
                v=parent[v]
        for nv in edge[x]:
            if nv!=parent[x]:
                sub.append(nv)

        if not q:
            q=sub
            sub=[]
            break

ans=0
for u in antena:
    if len(edge[u])==1:
        ans+=1
    elif len(edge[u])==2:
        check=0
        for v in edge[u]:
            check+=(v in antena)
        if check==1:
            ans+=1
    else:
        check=0
        for v in edge[u]:
            check+=(v in antena)
        if check>=len(edge[u])-1:
            continue
        else:
            ans+=len(edge[u])-1-check
print(ans)
### BUGGY CODE ###

def main():
  _max = max
  _range = range
  _input = input
  h, w = map(int, _input().split())
  s = [_input() + '#' for _ in _range(h)]
  s.append('#' * (w + 1))

  rt = [[-1] * w for _ in _range(h + 1)]
  tstart = [-1] * (w + 1)
  for i in _range(h + 1):
    si = s[i]
    rti = rt[i]
    ystart = -1
    for j in _range(w + 1):
      tj = tstart[j]
      if si[j] == '#':
        if ystart != -1:
          jy = j - ystart
          for k in _range(ystart, j):
            rti[k] += jy
          ystart = -1
        if tj != -1:
          itj = i - tj
          for k in _range(tj, i):
            rt[k][j] += itj
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tj == -1:
          tstart[j] = i

  print(_max(map(_max, rt)))

main()


### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

import numpy as np
from numba import njit


@njit("i8(i4,i4,i4[:],i4[:])")
def solve(N, K, P, L):
    ans = -np.iinfo(np.int64).min

    for i in range(N):
        score_acc = np.array([L[i]], dtype=np.int64)
        cur = P[i] - 1
        while cur != i:
            score_acc = np.append(score_acc, [L[cur]])
            cur = P[cur] - 1
        score_acc = np.cumsum(score_acc)
        M = len(score_acc)
        if M < K and score_acc[-1] > 0:
            res = K // M * score_acc[-1]
            if K % M:
                res += max(score_acc[: K % M])
            else:
                res += -score_acc[-1] + max(score_acc)
            ans = max(ans, res)
        else:
            res = max(score_acc[:K])
            ans = max(ans, res)
    return ans


N, K = map(int, input().split())
P = np.array(input().split(), dtype=np.int32)
L = np.array(input().split(), dtype=np.int32)
print(solve(N, K, P, L))


### FIXED CODE ###

from itertools import accumulate


def solve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    L = list(map(int, input().split()))

    ans = -float("inf")
    for i in range(N):
        score_acc = [L[i]]
        cur = P[i] - 1
        while cur != i:
            score_acc.append(L[cur])
            cur = P[cur] - 1
        score_acc = list(accumulate(score_acc))
        M = len(score_acc)
        if M < K and score_acc[-1] > 0:
            res = K // M * score_acc[-1]
            if K % M:
                res += max(score_acc[: K % M])
            else:
                res += -score_acc[-1] + max(score_acc)
            ans = max(ans, res)
        else:
            res = max(score_acc[:K])
            ans = max(ans, res)
    return ans


print(solve())
### BUGGY CODE ###

from math import floor,log10
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N,M = read_int()

A = read_int()
# for index arrangement
A.append(-1)
A.sort()

W = [0,2,5,5,4,5,6,3,7,6]

dp = [-1 for j in range(N+1)]
def solve():
    dp[0] = 0
    for i in range(M):
        for j in range(N+1):
            v = A[i + 1]
            if j - W[A[i + 1]] >= 0 and dp[j - W[A[i + 1]]] >= 0:
                d = 0
                if dp[j - W[A[i + 1]]] > 0:
                    d = len(str(dp[j - W[A[i + 1]]]))
                v = A[i + 1]*10**d
                dp[j] = max(dp[j], dp[j - W[A[i + 1]]] + v)

                
if __name__ == "__main__":
    solve()
    print(dp[N])

### FIXED CODE ###

from math import ceil,log10
import sys
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N,M = read_int()

A = read_int()
# for index arrangement
A.sort(reverse=True)
A.insert(0,-1)

W = [0,2,5,5,4,5,6,3,7,6]

dp = [-1 for j in range(N+1)]
def solve():
    dp[0] = 0
    for i in range(M):
        digit = [0 for _ in range(N+1)]
        for j in range(N+1):
            if j - W[A[i + 1]] >= 0 and dp[j - W[A[i + 1]]] >= 0:
                dp[j] = max(dp[j], dp[j - W[A[i + 1]]]*10 + A[i + 1])
                
if __name__ == "__main__":
    solve()
    print(dp[N])
### BUGGY CODE ###

def factors(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n /= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

import itertools, copy

def powerset(L):
  pset = set()
  for n in range(len(L) + 1):
    for sset in itertools.combinations(L, n):
      pset.add(sset)
  return pset
    
def list_diff(first, second):
        first = copy.copy(first)
        for s in second:
            first.remove(s)
        return first

def prod(lst):
    ret = 1
    for a in lst:
        ret *= a
    return ret

def main():
    N = int(input())
    facs = factors(N)
    st = powerset(facs)

    mn_ij = 10**12
    for i in st:
        i = list(i)
        j = list_diff(facs, i)
        i, j = prod(i), prod(j)

        mn_ij = min(mn_ij, i+j)

    print(int(mn_ij-2))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math

def main():
    N = int(input())
    rt_N = math.ceil(math.sqrt(N))

    mn_ij = 10**12
    for i in range(1, rt_N+1):
        if N % i == 0:
            j = N // i

            mn_ij = min(mn_ij, i+j)
        
        mn_ij = min(mn_ij, i+j)

    # print(list(map(len,[ st, facs]) ))
    print(int(mn_ij-2))

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

s = input()
q = int(input())

#一番最後に1度だけ反転すればよい
reverse_count = 0
for i in range(q):
  y = input().split()
  if y[0] == '1':
    s = s[::-1] 
  elif y[0] == '2':
    if y[1] == '1':
      #文字列の先頭に追加。反転回数が奇数なら、末尾に追加と同義
      if reverse_count % 2 == 1:
        s = s + y[2]
      else:
        s = y[2] + s
    elif y[1] == '2':
      #文字列の末尾に追加。反転回数が奇数なら、先頭に追加と同義
      if reverse_count % 2 == 1:
        s = y[2] + s
      else:
        s = s + y[2] 

#最後に一度だけ反転させる
if reverse_count % 2 == 0:
  #元の順序に戻るので、そのまま
  print(s)
else:
  print(s[::-1])



### FIXED CODE ###

from collections import deque
#双方向リストにするため、dequeを使用する
#（先頭と末尾に文字を追加するため）
s = deque(input())
q = int(input())

#一番最後に1度だけ反転すればよい
reverse_count = 0
for i in range(q):
  y = input().split()
  if y[0] == '1':
    #反転は最後に行う
    reverse_count += 1
    continue
  elif y[0] == '2':
    if y[1] == '1':
      #文字列の先頭に追加。反転回数が奇数なら、末尾に追加と同義
      if reverse_count % 2 == 1:
        s.append(y[2])
      else:
        s.appendleft(y[2])
    elif y[1] == '2':
      #文字列の末尾に追加。反転回数が奇数なら、先頭に追加と同義
      if reverse_count % 2 == 1:
        s.appendleft(y[2])
      else:
        s.append(y[2])

#最後に一度だけ反転させる
if reverse_count % 2 == 0:
  #元の順序に戻るので、そのまま
  print("".join(s))
else:
  s.reverse()
  print("".join(s))
### BUGGY CODE ###

h, w = map(int, input().split())

l = [input() for i in range(h)]
memo = [[False]*w for i in range(h)]

queue = []
sa = queue.append
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            sa((i, j))
            memo[i][j] = True

cl = [[True]*w for i in range(h)]

ql = []
qa = ql.append
count = 0
while 1:
    if memo == cl:
        print(count)
        break
    for i in queue:
        qa(i)
    queue = []
    sa = queue.append
    
    for nh, nw in ql:
        if nh > 0:
            if l[nh-1][nw] != "#":
                if memo[nh-1][nw] == False:
                    sa((nh-1, nw))
                    memo[nh-1][nw] = True
        if nw > 0:
            if l[nh][nw-1] != "#":
                if memo[nh][nw-1] == False:
                    sa((nh, nw-1))
                    memo[nh][nw-1] = True
        if nh < h-1:
            if l[nh+1][nw] != "#":
                if memo[nh+1][nw] == False:
                    sa((nh+1, nw))
                    memo[nh+1][nw] = True
        if nw < w-1:
            if l[nh][nw+1] != "#":
                if memo[nh][nw+1] == False:
                    sa((nh, nw+1))
                    memo[nh][nw+1] = True

    count += 1

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())

l = [input() for i in range(h)]
memo = [[-1]*w for i in range(h)]

black_cells = deque()
for i in range(h):
    for j in range(w):
        if l[i][j] == "#":
            black_cells.append((i, j))
            memo[i][j] = 0

count = 0
while black_cells:
    nh, nw = black_cells.popleft()
    count = memo[nh][nw]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_nh = nh + dy
        new_nw = nw + dx
        if new_nh < 0 or h <= new_nh or new_nw < 0 or w <= new_nw:
            continue
        if memo[new_nh][new_nw] == -1:
            memo[new_nh][new_nw] = count + 1
            black_cells.append((new_nh, new_nw))
print(count)
### BUGGY CODE ###

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

s = []
for i in range(1001):
    s.append(0.5+(0.5*i))

t = []
for i in p:
    t.append(s[i])

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

print(ans)

### FIXED CODE ###

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

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

print(0.5+(0.5*ans)+(k-1)*0.5)
### BUGGY CODE ###


def solve():
    N, X, M = map(int, input().split())

    _l = tuple([i**2 % M for i in range(M)])

    _a = X
    ans_l = [0] * M
    ans_l[0] = _a
    seq = [_a]
    s = g = 0
    for i in range(1, M):
        _a = _l[_a]
        ans_l[i] = _a + ans_l[i-1]
        if _a in seq:
            s = seq.index(_a)
            g = len(seq)-1
            break
        seq.append(_a)
    _tmp = N - s
    loop = _tmp // (g - s + 1)
    zan = _tmp % (g - s + 1)
    ans = ans_l[s-1] + (ans_l[g] - ans_l[s-1]) * loop + \
        (ans_l[s+zan-1] - ans_l[s-1])
    print(ans)


solve()


### FIXED CODE ###


def solve():
    N, X, M = map(int, input().split())

    _l = tuple([i**2 % M for i in range(M)])

    _a = X
    ans_l = [0] * M
    ans_l[0] = _a
    seq = [_a]
    s = g = 0
    for i in range(1, M):
        _a = _l[_a]
        ans_l[i] = _a + ans_l[i-1]
        if _a in seq:
            s = seq.index(_a)
            g = len(seq)-1
            break
        seq.append(_a)
    _tmp = N - s
    loop = _tmp // (g - s + 1)
    zan = _tmp % (g - s + 1)
    ans = ans_l[s-1] + (ans_l[g] - ans_l[s-1]) * loop + \
        (ans_l[s+zan-1] - ans_l[s-1])
    print(ans)


solve()
### BUGGY CODE ###

h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))

tate=[[-1 for _ in range(w)] for _ in range(h)]
yoko=[[-1 for _ in range(w)] for _ in range(h)]

def search(i,j):
    ansij=1

    if(yoko[i][j] == -1):
        xl=j
        while(0<xl and s[i][xl-1]=='.'):
            ansij+=1
            xl-=1
        xr=j
        while(xr<w-1 and s[i][xr+1]=='.'):
            ansij+=1
            xr+=1

        for k in range(xl,xr+1):
            yoko[i][k]=xr-xl
    else:
        ansij+=yoko[i][j]

    if(tate[i][j] == -1):
        yu=i
        while(0<yu and s[yu-1][j]=='.'):
            ansij+=1
            yu-=1
        yd=i
        while(yd<h-1 and s[yd+1][j]=='.'):
            ansij+=1
            yd+=1

        for k in range(yu,yd+1):
            tate[k][j]=yd-yu
    else:
        ansij+=tate[i][j]

    return ansij

ans=0
for i in range(h):
    for j in range(w):
        if(s[i][j]=='.'):
            ansij=search(i, j)
            if(ans<ansij):
#                print(i,j,ansij)
                ans=ansij

print(ans)


### FIXED CODE ###

import numpy as np
h,w=map(int,input().split())
s=[]
for _ in range(h):
    si=input()
    si=si.replace('.', '1')
    si=si.replace('#', '0')
    s.append(list(map(int,si)))
s=np.array(s)

left=np.zeros((h,w))
right=np.zeros((h,w))
up=np.zeros((h,w))
down=np.zeros((h,w))

for i in range(w):
    if(i==0):
        left[:,i]=s[:,i]
        right[:,w-i-1]=s[:,w-i-1]
    else:
        left[:,i]=(left[:,i-1]+1)*s[:,i]
        right[:,w-i-1]=(right[:,w-i]+1)*s[:,w-i-1]

for i in range(h):
    if(i==0):
        down[i,:]=s[i,:]
        up[h-i-1,:]=s[h-i-1,:]
    else:
        down[i,:]=(down[i-1,:]+1)*s[i,:]
        up[h-i-1,:]=(up[h-i,:]+1)*s[h-i-1,:]

ans=left+right+up+down-3
print(int(np.max(ans)))
### BUGGY CODE ###

import time
def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]
    start = time.time()
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        if time.time() - start > 1.8:
            print((N*(N-1))//2)
            break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import time
def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]
    start = time.time()
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        if time.time() - start > 1.6:
            print((N*(N-1))//2)
            break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

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

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

L.sort()
L.reverse()
#print(L)
count=0

for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if L[k]>L[i]-L[j]:
          count +=1
      else:
        break
            
print(count)
        


### FIXED CODE ###

import bisect

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

L.sort()
#print(L)
count=0

for i in reversed(range(2,N)):
  for j in reversed(range(1,i)):
    index=bisect.bisect_right(L,L[i]-L[j])
    #print(index,j,i)
    if index<j:
     count += j-index
            
print(count)
### BUGGY CODE ###

n, a, b = map(int, input().split())
res = 0

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

from functools import lru_cache

@lru_cache(maxsize=1000)
def c(n,k): 
    return 1 if(k<=0 or n<=k) else ( c(n-1, k-1) + c(n-1, k) ) %4

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

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

res -= cmb(n,a,mod)
res -= cmb(n,b,mod)

print(res)


### FIXED CODE ###

n, a, b = map(int, input().split())

mod = 10**9 + 7
res = pow(2, n, mod)

def cmb(n, r, mod):
    r = min(n-r, r)
    if r == 0:
        return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    inv = pow(under, mod-2, mod)
    return over * inv % mod


A = cmb(n, a, mod)
B = cmb(n, b, mod)

print((res - A - B - 1) % mod)
### BUGGY CODE ###

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

ans = 1
for i in range(n):
    ans *= a[i]
    
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

# B  => TLE
n = int(input())
a = list(map(int, input().split()))

ans = 1
if a.count(0) > 0:
    ans = 0
else:
    for i in range(n):
        ans *= a[i]
        if ans > 10**18:
            ans = -1
            break
    
print(ans)
### BUGGY CODE ###

def dijkstra(s,n,w,cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

n,m = map(int,input().split())

cost = [[float("inf") for i in range(n)] for i in range(n)] 
for i in range(m):
    x,y,z = map(int,input().split())
    cost[x-1][y-1] = z
    cost[y-1][x-1] = z
for i in range(1,n):
    cost[i][i-1]=0
x=dijkstra(0,n,m,cost)[n-1]
if x==float("inf"):
  print(-1)
else:
  print(x)

### FIXED CODE ###

import heapq
def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


n,m = map(int,input().split())

edge = [[] for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1]) 
for i in range(1,n):
  edge[i].append([0,i-1])
x=dijkstra_heap(0)[n-1]
if x==float("inf"):
  print(-1)
else:
  print(x)
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]
S = [sum(A[:i]) for i in range(n+1)]
# num = [S.count(i) for i in set(S)]

from collections import Counter
def hello(bm):
    dt = Counter()
    for i in bm:
        key = str(i)
        dt[key] += 1
    return dt

num = hello(S)
out = [i*(i-1)//2 for i in num.values() if i>1]
print(sum(out))

### FIXED CODE ###

from collections import Counter
n = int(input())
A = [int(i) for i in input().split()]
S = [0]*(n+1)
for i in range(n):
    S[i+1] = S[i] + A[i]
def hello(data):
    dt = Counter()
    for i in data:
        dt[str(i)] += 1
    return dt
num = hello(S)
out = [i*(i-1)//2 for i in num.values() if i>1]
print(sum(out))
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 1 #i=1は常に成り立つ
 
for i in range(1, n): #i=2以降について順番に見ていく
  for j in range(0, i): #iより小さい要素について順番に見ていく
    if p[j] < p[i]: #jの方が小さかったら
      break #ダメなので抜ける
    if j == i-1: #j=i-1になったら
      ans = ans + 1 #要件を満たすので+1する
  
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
mini = p[0]
ans = 1

for i in p:
    if i < mini:
        ans += 1
        mini = i

print(ans)