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

# coding: utf-8

def greatest_common_divisor(a, b):
    assert a >= b
    while b != 0:
        a, b = b, a%b
    return a

def main():
    a, b = input().split()
    a, b = int(a), int(b)

    if a == 1 or b == 1:
        print(1)
        exit()

    if b > a:
        a, b = b, a

    relative_primes = []
    gcd = greatest_common_divisor(a, b)
    for i in range(2, gcd+1):
        if gcd % i > 0:
            continue
            
        flg = True
        for rp in relative_primes:
            if i % rp == 0:
                flg = False
                continue
        if flg:
            relative_primes.append(i)
    print(len(relative_primes)+1)
    

main()

### FIXED CODE ###

# coding: utf-8

def greatest_common_divisor(N, M):
    assert N >= M
    while M != 0:
        N, M = M, N%M
    return N

def prime_divisor(N):
    temp = N
    for n in range(2, int(-(-N**0.5//1))+1):
        if temp % n == 0:
            while temp % n == 0:
                temp //= n
            yield n
    if temp != 1:
        yield temp
        

def main():
    a, b = input().split()
    a, b = int(a), int(b)

    if a > b:
        a, b = b, a

    gcd = greatest_common_divisor(b, a)
    pdiv = [pd for pd in prime_divisor(gcd)]
    print(len(pdiv)+1)

main()
### BUGGY CODE ###

n, y = map(int, input().split())
y /= 1000
flag = 0

a = 0
while 10*a <= y:
  b = 0
  while 5*b + 10*a <=y:
    r = y - 10*a - 5*b
    if n == a + b + r:
      print(a, b, int(r))
      flag = 1
      break
    b += 1
  if flag == 1:
    break
  a += 1
  
if flag == 0:
  print(-1)
  print(-1)
  print(-1)
  
    
  

### FIXED CODE ###

n,y = map(int,input().split())
y //= 1000
flag = False

for k in range(0,n+1):
  a = n-k
  b = y-10*k-a
  if b%4 == 0 and b <= 4*a and b>=0:
    flag = True
    break
    
if flag:
  print(k,b//4,a-b//4)
else:
  print(-1,-1,-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
 
from fractions import gcd
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
 
ans=0
for i in range(n):
    ans+=lcm//a[i]
 
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
 
from fractions import gcd
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
 
ans=0
for i in range(n):
    ans+=lcm//a[i]
 
print(ans%(10**9+7))
### BUGGY CODE ###

n, k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort(reverse=True)

seed = h[0]
for i in range(0,n-k+1):
    high = h[i:i+k][0] - h[i:i+k][k-1]
    seed = min(high,seed)

print(seed)

### FIXED CODE ###

n, k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort(reverse=True)

seed = h[0]
for i in range(0,n-k+1):
    high = h[i] - h[i+k-1]
    seed = min(high,seed)

print(seed)
### BUGGY CODE ###

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

i=0
while i < N:

    j=i+1
    while j < N:
        if x[i]==x[j]:
            del x[j]
            del x[i]
            N-=2
            i-=1
            break
        j+=1
    i+=1


print(len(x))

### FIXED CODE ###


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

x.sort()
i=0
while i < N-1:
    if x[i]==x[i+1]:
        del x[i+1]
        del x[i]
        N-=2
        continue
    i+=1
print(len(x))
### BUGGY CODE ###

from functools import lru_cache

def main(S):
    con = 10**9 + 7

    @lru_cache(maxsize=1024, typed=True)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[(_r + r) % 13] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

    ans = pdp.get(5, 0)
    print(ans % con)

if __name__ == "__main__":
    S = input()
    main(S)

### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline


def warshall_floyd(D, n):
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    D[i][j] = min(D[i][j], D[i][k]+D[k][j])


def main():
    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    D = [[float('inf')]*N for _ in range(N)]
    for i in range(N):
        D[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        D[a-1][b-1] = c
        D[b-1][a-1] = c

    warshall_floyd(D, N)

    ans = float('inf')
    for P in itertools.permutations(r):
        cost = 0
        for i in range(R-1):
            cost += D[P[i]-1][P[i+1]-1]
        ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import itertools

def warshall_floyd(D, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                D[i][j] = min(D[i][j], D[i][k]+D[k][j])


N, M, R = map(int, input().split())
r = list(map(int, input().split()))
D = [[float('inf')]*N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    D[a-1][b-1] = c
    D[b-1][a-1] = c

warshall_floyd(D, N)

ans = float('inf')
for P in itertools.permutations(r):
    cost = 0
    for i in range(R-1):
        cost += D[P[i]-1][P[i+1]-1]
    ans = min(ans, cost)

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

N = int(input())
a = [0] * 2050
for i in range(200010):
    a[N % 2019] += 1
    N //= 10**(i+1)
    N *= 10**(i+1)
    if N <= 0:
        break
ans = 0
for i in range(2019):
    if i == 0:
        ans += a[i] * (a[i]+1) // 2
    else:
        ans += (a[i]-1) * a[i] // 2
print(ans)


### FIXED CODE ###

N = input()
a = [0] * 2050
n = 0
p = 1
for i in range(len(N)):
    n += int(N[len(N)-1-i]) * p
    p *= 10
    p %= 2019
    a[int(n) % 2019] += 1
ans = 0
for i in range(2019):
    if i == 0:
        ans += a[i] * (a[i]+1) // 2
    else:
        ans += (a[i]-1) * a[i] // 2
print(ans)
### BUGGY CODE ###

# coding: utf-8
n = int(input())
a_list = list(map(int,input().split()))
ans_list = []

#a0
ans_flag = 0
first_ans = a_list[0]
for i in range(1,n-1):
    if ans_flag == 1:
        break
    for j in range(i+1,n):
        ans = a_list[i] ^ a_list[j]
        #print(ans)
        if ans == a_list[0]:
            ans_flag = 1
            fin_ans = a_list[j]
            sec_ans = a_list[i]
            a_list.remove(sec_ans)
            a_list.remove(fin_ans)
            a_list.remove(first_ans)
            ans_list.append(first_ans)
            ans_list.append(sec_ans)
            break
        
if ans_flag == 0:
    print("No")
    quit()

for i in range(n-2):
    ans = ans_list[i] ^ ans_list[i+1]
    if i == n-3:
        if ans == fin_ans:
            print("Yes")
            quit()
    
    if ans in a_list:
        ans_list.append(ans)
        a_list.remove(ans)
    else:
        print("No")
        quit()
    

### FIXED CODE ###

# coding: utf-8
import collections
 
n = int(input())
a_list = list(map(int,input().split()))
 
c = collections.Counter(a_list)
 
#print(len(c.keys()))
ans_list = list(c.keys())
count_list = list(c.values())
 
#print(c.keys())
if len(c.keys()) == 1:
    if list(c.keys()) == [0]:
        print("Yes")
        quit()
    else:
        print("No")
        quit()
elif len(c.keys()) == 2:
    if ans_list[0] == ans_list[0]^ans_list[1] and count_list[0]== 2*count_list[1]:
        print("Yes")
        quit()
    elif ans_list[1] == ans_list[0]^ans_list[1] and count_list[1]== 2*count_list[0]:
        print("Yes")
        quit()
    else:
        print("No")
        quit()
        
if len(c.keys()) != 3:
    print("No")
    quit()

count_list.sort()
if ans_list[0] == ans_list[1] ^ ans_list[2]:
    if count_list[0]==count_list[1]==count_list[2]:
        print("Yes")
    else:
        print("No")
else:
    print("No")
### BUGGY CODE ###

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

ans = 1
for i in range(n):
    ans*=A[i]
if ans>1e18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
A.sort()
if A[0]==0:
    print(0)
    exit()

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

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for m in range(M):

    B, C = map(int, input().split())
    assi = min(len(A), B)-1

    if A[assi] <= C:
        A[0:assi+1] = [C for c in range(assi+1)]
        A.sort()
    else:
        for a in range(assi):
            if A[a] >= C:
                break
            A[a] = C

print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
p = [(A[i], 1) for i in range(N)]
for m in range(M):
    B, C = map(int, input().split())
    p.append((C, B))

p.sort()
p.reverse()

ans = 0
for v, n in p:
    use = min(N, n)
    ans += use * v
    N -= use
    if N == 0:
        break
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
h_array = list(map(int, input().split()))
ab = []
sum = 0

for i in range(m):
  ab.append(list(map(int, input().split())))

for i in range(1, n + 1):
  array = [element for element in ab if element[0] == i or element[1] == i]
  array.sort()
  result = True
  for j in range(len(array)):
    if (i == array[j][1]):
      if h_array[array[j][0]- 1] >= h_array[i - 1]:
        result = False
    else:
      if h_array[array[j][1]- 1] >= h_array[i - 1]:
        result = False
  if result:
    sum += 1

print(sum)

### FIXED CODE ###

n, m = map(int, input().split())
h_array = list(map(int, input().split()))
ab = []
sum = 0
answer = [True for i in range(n)]

for i in range(m):
  ab.append(list(map(int, input().split())))

for i in range(len(ab)):
  if h_array[ab[i][0]- 1] >= h_array[ab[i][1]- 1]:
    answer[ab[i][1] - 1] = False
  if h_array[ab[i][1]- 1] >= h_array[ab[i][0]- 1]:
      answer[ab[i][0] - 1] = False

print(answer.count(True))
### BUGGY CODE ###

from collections import Counter


def check(s1, s2, i, j, memo):
    if memo[i] == -1:
        if memo[j] == -1:
            if s1 == s2:
                memo[i] = i
                memo[j] = i
                return 1
            else:
                return 0
        else:
            return 0
    else:
        if memo[j] == -1:
            if s1 == s2:
                memo[j] = i
                return 1
        elif memo[i] == memo[j]:
            return 1

    return 0


def main():
    N = int(input())

    S = []
    for _ in range(N):
        s = input()
        S.append(Counter(s))

    ans = 0
    memo = [-1 for i in range(N)]
    for i in range(N):
        for j in range(i+1, N):
            if len(S[i]) == len(S[j]):
                ans += check(S[i], S[j], i, j, memo)

    print(ans)


main()

### FIXED CODE ###

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
ans_dict = {}

for _ in range(n):
    s = list(input())
    s.sort()
    s = ''.join(s)
    try:
        ans_dict[s] += 1
    except:
        ans_dict[s] = 1

ans = 0
for key in ans_dict:
    if ans_dict[key] >= 2:
        ans += combinations_count(ans_dict[key], 2)
print(ans)
### BUGGY CODE ###

import copy
def main():
    N = int(input())
    A = [int(input()) for a in range(N) ]
    for i in range(N):
        tmp = copy.copy(A[i])
        A[i] = 0
        print(max(A))
        A[i] = copy.copy(tmp)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import copy
def main():
    N = int(input())
    A = [int(input()) for a in range(N) ]
    C = sorted(A)
    Af = C[-1]
    As = C[-2]

    for i in range(N):
        if A[i] != Af:
            print(Af)
        else:
            print(As)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 9)

@lru_cache(maxsize=None)
def fib(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

PRIME = 10 ** 9 + 7
N, M = list(map(int, input().split()))
broken_stairs = []
for _ in range(M):
    broken_stairs.append(int(input()))

prev_broken = -1
cannot = False
ans = 1
for a in broken_stairs:
    if a - prev_broken == 1:
        cannot = True
        break
    ans *= fib(a - prev_broken - 2)
    ans %= PRIME
    prev_broken = a

ans *= fib(N - prev_broken - 1)
ans %= PRIME

if cannot:
    print(0)
else:
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def fib_memo(n):
    if n <= 1:
        return 1
    memo = [0] * n
    memo[0] = 1
    memo[1] = 2
    for i in range(2, n):
        memo[i] = (memo[i - 1] + memo[i - 2]) % PRIME
    return memo[n-1]

PRIME = 10 ** 9 + 7
N, M = list(map(int, input().split()))
broken_stairs = []
for _ in range(M):
    broken_stairs.append(int(input()))

prev_broken = -1
cannot = False
ans = 1
for a in broken_stairs:
    if a - prev_broken == 1:
        cannot = True
        break
    ans *= fib_memo(a - prev_broken - 2)
    ans %= PRIME
    prev_broken = a

ans *= fib_memo(N - prev_broken - 1)
ans %= PRIME

if cannot:
    print(0)
else:
    print(ans)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

dp = Counter()

dp[0] = 0
dp[1] = 1

geta = 1000
geta2 = geta**2
CA = Counter(A)
SA = CA[1]
SB = CA[2]
SC = CA[3]
for c in range(SC+1):
    for b in range(SB+SC+1):
        if b + c > N:
            break
        for a in range(N+1):
            if a + b + c > N:
                break
            S = a + b + c
            if S == 0:
                continue
            res = N/S
            res += a/S*dp[(a-1)*geta2 + b*geta + c]
            res += b/S*dp[(a+1)*geta2 + (b-1)*geta + c]
            res += c/S*dp[a*geta2 + (b+1)*geta + c - 1]
            dp[a*geta2 + b*geta + c] = res

print(dp[SA*geta2 + SB*geta + SC])

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
CA = Counter(A)
SA = CA[1]
SB = CA[2]
SC = CA[3]
for c in range(SC+1):
    for b in range(SB+SC+1):
        if b + c > N:
            break
        for a in range(N+1):
            if a + b + c > N:
                break
            S = a + b + c
            if S == 0:
                continue
            dp[a][b][c] = N/S + a/S*dp[a-1][b][c]\
            +b/S*dp[a+1][b-1][c]\
            +c/S*dp[a][b+1][c - 1]

print(dp[SA][SB][SC])
### BUGGY CODE ###

import bisect



def find_num(lst, num):
    insert_index = bisect.bisect_left(lst, num)
    return insert_index


n = int(input())
l = list(map(int, input().split()))
l.sort()
cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        cnt += find_num(lst=l[j+1:], num=l[i] + l[j])
print(cnt)


### FIXED CODE ###

import bisect



def find_num(lst, num):
    insert_index = bisect.bisect_left(lst, num)
    return insert_index


n = int(input())
l = list(map(int, input().split()))
l.sort()
cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        cnt += find_num(lst=l[j+1:], num=l[i] + l[j])
print(cnt)
### BUGGY CODE ###

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

for x in range(k):
  if a >= 1:
    a -= 1
  elif b >= 1:
    b -= 1
  else:
    break

print(a,b)

### FIXED CODE ###

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

if a >= k :
  print(a-k,b)
  
elif a + b >= k:
  print(0,b-k+a)

else:
  print(0,0)
### BUGGY CODE ###

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

tyouten = [list(map(int,input().split())) for _ in range(n-1)]
tree = [list(map(int,input().split())) for _ in range(q)]
ans = [0] * n
temp = [[] for i in range(1,n+1)]
temp2 = [[0] for _ in range(n)]

tyouten.sort()

for i in range(n-1):
    temp[tyouten[i][0]-1].append(tyouten[i][1])

for i in range(q):
    temp2[tree[i][0]-1][0] += tree[i][1]
    
for i in range(n):
    ans[i] += temp2[i][0]
    for j in temp[i]:
        ans[j-1] += ans[i]
    
print(*ans)


### FIXED CODE ###

n, q = map(int, input().split())
li_nq = [list(map(int, input().split())) for _ in range(n-1)]
li_px = [list(map(int, input().split())) for _ in range((q))]

graph = [[] for _ in range(n+1)]
for i, j in li_nq:
    graph[i].append(j)
    graph[j].append(i)

ans = [0 for _ in range(n+1)]
for i, j in li_px:
    ans[i] += j

check_list = [None] * (n+1)
stack = [1]

while stack:
    num = stack.pop()
    for i in graph[num]:
        if check_list[num] == i:
            continue
        stack.append(i)
        ans[i] += ans[num]
        check_list[i] = num

print(*ans[1:])
### BUGGY CODE ###

def xor(stra, strb):
    ans = ""
    for i in range(len(stra)):
        if (stra[i] == '0' and strb[i] =='0') or (stra[i] =='1' and strb[i] =='1'):
            ans += str(0)
        else:
            ans += str(1)
    return ans

a, b= map(int, input().split())
lista = []
cri = len(str(bin(b).split("b")[1]))
for i in range(a, b+1):
    if len(str(bin(i).split("b")[1])) < cri:
        diff = cri - len(str(bin(i).split("b")[1]))
        tmp = ""
        for j in range(diff):
            tmp += str(0)
        lista.append(tmp +str(bin(i).split("b")[1]))
    else:
        lista.append(bin(i).split("b")[1])

ans = lista[0]
for i in range(1, len(lista)):
    ans = xor(ans, lista[i])
    
print(int(ans,2))

### FIXED CODE ###

import numpy as np
a, b= map(int, input().split())
if a % 2 ==0:
    start = a
    remain_before = 0
else:
    start = a+1
    remain_before = a

if b % 2 ==0:
    end = b-1
    remain_after = b
else:
    end = b
    remain_after = 0

if ((end+1-start) /2) %2 == 0:
    num = 0
else:
    num = 1

print(remain_before ^ num ^ remain_after)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
p = 0
if n <= 2:
    if a[0] < a[1]:
        exit(print('Yes'))
    else:
        exit(print('No'))
p = 1
for i in range(k): p *= a[i]
for i in range(k,n):
    t = p * a[i]
    p *= a[i-k]
    if p < t:
        print('Yes')
    else:
        print('No')
    p = t


### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(k,n): print('Yes' if a[i] > a[i-k] else 'No')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    ed.append([a, b])

col = max(len(v) for v in adj)
cand = set([v for v in range(1, col+1)])

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, -1]]
cnt = 0
while Q and cnt < N-1:
    cur, prev, NG = Q.pop()
    for nex, c in zip(adj[cur]-{prev}, cand-{NG}):
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
        cnt += 1
print(col)
for a, b in ed:
    print(colors[a*N + b])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [set() for _ in range(N)]
colors = dict()
ed = []
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].add(b)
    adj[b].add(a)
    ed.append([a, b])

col = max(len(v) for v in adj)

s = -1
for i, a in enumerate(adj):
    if len(a) == col:
        s = i
        break

Q = [[s, -1, -1]]
while Q:
    cur, prev, NG = Q.pop()
    c = 0
    for nex in adj[cur]:
        if nex == prev:
            continue
        else:
            c += 1
        if c == NG:
            c += 1
        colors[min(cur, nex)*N + max(cur, nex)] = c
        Q.append([nex, cur, c])
print(col)
for a, b in ed:
    print(colors[a*N + b])
### BUGGY CODE ###

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**4+5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))


### FIXED CODE ###

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**4+5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
count=1
for i in range(1,n):
    if p[i]<=min(p[:i+1]):
        count+=1
print(count)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
count=0
pmin=float('inf')
for i in range(n):
    pmin=min(pmin,p[i])
    if p[i]<=pmin:
        count+=1
print(count)
### BUGGY CODE ###

import collections
N, M = map(int, input().split())
p = list(map(int, input().split()))

xy = [tuple(map(int, input().split())) for i in range(M)]

table = collections.defaultdict(set)

table2 = collections.defaultdict(int)
ans = 0
for i, x in enumerate(p):
    if i+1 == x:
        ans += 1
    else:
        table2[i + 1] = x
id = 0
for x, y in xy:
    a, b = -1, -1
    for z in table:
        if x in table[z]:
            a = z
            break
    for z in table:
        if y in table[z]:
            b = z
            break
    if a == b:
        if a == -1:
            table[id].add(x)
            table[id].add(y)
            id += 1
    elif a == -1 or b == -1:
        if a == -1:
            table[b].add(x)
        else:
            table[a].add(y)
    else:
        table[a] |= (table[b])
        del(table[b])

for x in table:
    for a in table[x]:
        if a in table2 and table2[a] in table[x]:
            ans += 1
print(ans)


### FIXED CODE ###

import collections
import sys


class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

    def same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return


input = sys.stdin.readline
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [tuple(map(int, input().split())) for i in range(M)]
ans = 0
t = unionFind(N)

for x, y in xy:
    t.unite(x, y)

for i in range(N):
    if t.same(i+1, p[i]):
        ans += 1
print(ans)