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

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

mod = 1000000007

result = [-1]*(N+1)

result[0] = 1
result[1] = 1

for a in a_list:
    result[a] = 0

for i in range(2, N+1):
    if i not in a_list:
        result[i] = (result[i-1]+result[i-2])%mod
        if result[i] == 0:
            result[-1] = 0
            break
    
print(result[-1])

### FIXED CODE ###

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

mod = 1000000007

DP = [-1] * (N + 1) 
DP[0] = 1 
DP[1] = 1 

def fib(n):
    for i in range(2, n + 1):
        DP[i] = DP[i-1] + DP[i-2]
    
    return DP[n]

ans = 1
x = 0

for a in a_list:
    if a == x:
        ans = 0
        break
    
    ans = (ans * fib((a-1)-x)) % mod
    x = a+1
else:
    ans = (ans * fib(N-x)) % mod
    
print(ans)
### BUGGY CODE ###

from collections import deque
import sys
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
count=0
queue=deque([[0,0,0]])
for i in range(h):
    for j in range(w):
        if field[i][j]=='.':
            count+=1
def bfs(x,y,k):
    if (not 0<=x<h) or (not 0<=y<w):
        return
    if field[x][y]=='#':
        return
    if visit[x][y]==1:
        return
    queue.append([x,y,k+1])
visit=[[0]*w for _ in range(h)]
while queue:
    x,y,k=queue.popleft()
#    print(queue)
#    print(field)
    if x==h-1 and y==w-1:
        print(count-k-1)
        sys.exit()
    
    visit[x][y]=1
    bfs(x+1,y,k)
    bfs(x-1,y,k)
    bfs(x,y-1,k)
    bfs(x,y+1,k)
if visit[h-1][w-1]==0:
    print(-1)
else:
    print(count-k-1)

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
field=[list(input()) for _ in range(h)]
cost=[[float('inf')]*w for _ in range(h)]
cost[0][0]=1
queue=deque([[0,0]])
count=0
for i in range(h):
    for j in range(w):
        if field[i][j]=='.':
            count+=1
def bfs():
    while queue:
        x,y=queue.popleft()
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            if 0<=x+dx<h and 0<=y+dy<w:
                if field[x+dx][y+dy]=='.' and cost[x+dx][y+dy]==float('inf'):
                    cost[x+dx][y+dy]=cost[x][y]+1
                    queue.append([x+dx,y+dy])
bfs()
#print(cost)
if cost[-1][-1]<float('inf'):
    print(count-cost[-1][-1])
else:
    print(-1)
### BUGGY CODE ###

h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])

dp = [[[False]*(80*(h+w)) for i in range(w)] for k in range(h)]
dp[0][0][mat[0][0]] = True
for y in range(h):
  for x in range(w):
      for k in range(80*(h+w)):
        if x > 0 and dp[y][x-1][k] or y > 0 and dp[y-1][x][k]:
          d = dp[y][x]
          d[k+mat[y][x]] = True
          d[abs(k-mat[y][x])] = True

for k in range(80*(h+w)):
  if dp[h-1][w-1][k]:
    print(k)
    exit()


### FIXED CODE ###

h, w = map(int, input().split())
mat = []
for i in range(h):
  a = list(map(int, input().split()))
  mat.append(a)
for i in range(h):
  b = list(map(int, input().split()))
  for j in range(w):
    mat[i][j] = abs(mat[i][j]-b[j])
m = max(map(max, mat))
dp = [[0b0 for i in range(w)] for k in range(h)]
dp[0][0] |= 0b1 << mat[0][0]
for y in range(h):
  for x in range(w):
        if x > 0:
          dp[y][x] |= dp[y][x-1] << mat[y][x]
          dp[y][x] |= dp[y][x-1] >> mat[y][x]
          anded = dp[y][x-1] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        if y > 0:
          dp[y][x] |= dp[y-1][x] << mat[y][x]
          dp[y][x] |= dp[y-1][x] >> mat[y][x]
          anded = dp[y-1][x] & int('1'*(mat[y][x]+1), 2)
          reverse = format(anded, "0"+str(mat[y][x]+1)+"b")[::-1]

          dp[y][x] |= int(reverse, 2)
        #print(bin(dp[y][x]))

keta = 0
while dp[h-1][w-1] % 2 == 0:
  keta += 1
  dp[h-1][w-1] //= 2
print(keta)
### BUGGY CODE ###

S=input()
Q=int(input())
Q=[input().split() for i in range(Q)]
 
for i in Q:
    if i[0]=='1':
        S=S[::-1]
    else:
        if i[1]=='1':
            S=i[2]+S
        else:
            S=S+i[2]
print(S)

### FIXED CODE ###

S=input()
Q=int(input())
Q=[input().split() for i in range(Q)]
Forward=[]
Backward=[]
count=0
for i in Q:
    if i[0]=='1':
        count+=1
    else:
        if (int(i[1])+count)%2==1:
            Forward.append(i[2])
        else:
            Backward.append(i[2])  
if count%2==0:
    ans = (''.join(Forward))[::-1]+S+(''.join(Backward))
else:
    ans = (''.join(Backward)[::-1]+S[::-1]+(''.join(Forward)))
print(ans)
### BUGGY CODE ###

import math as m
import fractions

A, B = list(map(int, input().split()))
#A , B = 12, 18

def sieve_of_eratosthenes(n):
    candidate = [1 for i in range(n+1)]
    candidate[0] = 0
    candidate[1] = 0
    for i in range(len(candidate)):
        if (candidate[i] == 0):
            continue
        j = 2
        while j * i < len(candidate):
            candidate[i * j] = 0
            j = j + 1
    primes = [i for i in range(n) if candidate[i] == 1]
    return primes

def prime_factorize(A):
    p = sieve_of_eratosthenes(m.floor(A**0.5))
    a = [0 for i in p]
    for i in range(len(p)):
        if A % p[i] != 0:
            a[i] = 0
        else:
            temp = A
            while temp % p[i] == 0:
                temp = temp / p[i]
                a[i] = a[i] + 1
    return a

#pf = prime_factorize(fractions.gcd(A, B))
# num = 1

# for x in pf:
#     if x >= 1:
#         num = num + 1



# print(num)

g = fractions.gcd(A,B)
primes = []
num = 1

if True:
    i = 2
    while i <= g:
        if (g % i == 0):
            cnt = 0
            while g % i == 0:
                cnt = cnt + 1
                g = g // i
            primes.append([i, cnt])
        i = i + 1


#print(primes)
print(len(primes)+1)


### FIXED CODE ###

import math as m
import fractions

A, B = list(map(int, input().split()))
#A , B = 12, 18

def sieve_of_eratosthenes(n):
    candidate = [1 for i in range(n+1)]
    candidate[0] = 0
    candidate[1] = 0
    for i in range(len(candidate)):
        if (candidate[i] == 0):
            continue
        j = 2
        while j * i < len(candidate):
            candidate[i * j] = 0
            j = j + 1
    primes = [i for i in range(n) if candidate[i] == 1]
    return primes

def prime_factorize(A):
    p = sieve_of_eratosthenes(m.floor(A**0.5))
    a = [0 for i in p]
    for i in range(len(p)):
        if A % p[i] != 0:
            a[i] = 0
        else:
            temp = A
            while temp % p[i] == 0:
                temp = temp / p[i]
                a[i] = a[i] + 1
    return a

#pf = prime_factorize(fractions.gcd(A, B))
# num = 1

# for x in pf:
#     if x >= 1:
#         num = num + 1



# print(num)

g = fractions.gcd(A,B)
primes = []
num = 1

if True:
    i = 2
    while i * i <= g:
        if (g % i == 0):
            cnt = 0
            while g % i == 0:
                cnt = cnt + 1
                g = g // i
            primes.append([i, cnt])
        i = i + 1
    if (g != 1):
        primes.append([g, 1])
print(len(primes)+1)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 0
for i in range(N):
    if P[i] <= min(P[:(i+1)]):
        ans += 1
print(ans)

### FIXED CODE ###

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

s = input()
q = int(input())
for i in range(q):
    t, *u= input().split()
    if t == "1":
        s = s[::-1]
    elif t == "2":
        f, c = u[0], u[1]
        if f == "1":
            s = c + s
        elif f == "2":
            s = s + c

print(s)


### FIXED CODE ###

s = input()
q = int(input())
d = True
head = []
tail = []
for i in range(q):
    t, *u= input().split()
    if t == "1":
        d = not d
    else:
        f, c = u[0], u[1]
        if d:
            if f == "1":
                head.append(c)
            else:
                tail.append(c)
        else:
            if f == "1":
                tail.append(c)
            else:
                head.append(c)
s = "".join(head)[::-1] + s + "".join(tail)
print(s if d else s[::-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import Counter

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 ** 18
MOD = 10 ** 9 + 7

def dfs(N, nodes, src):
    """ DFS(木、再帰、重みなし) """

    def rec(u, prev):
        C = Counter()
        for v in nodes[u]:
            if v != prev:
                C[rec(v, u) + 1] += 1
        if not C:
            return 0
        mx = max(C.keys())
        mn = min(C.keys())
        add = 0
        vacant = 0
        for i in range(mx, mn-1, -1):
            vacant -= C[i] - 1
            if vacant < 0:
                add += abs(vacant)
                vacant = 0
        return mx + add

    return rec(src, -1)

N = INT()
nodes = [[] for i in range(N)]
for a in range(1, N):
    b = INT()
    b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

print(dfs(N, nodes, 0))


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import Counter

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 ** 18
MOD = 10 ** 9 + 7

def get_sum(a, b, c):
    """ 等差数列の和：(初項a, 末項b, 項数c) """
    return (a+b) * c // 2

def dfs(N, nodes, src):
    """ DFS(木、再帰、重みなし) """

    def rec(u, prev):
        C = Counter()
        for v in nodes[u]:
            if v != prev:
                C[rec(v, u) + 1] += 1
        if not C:
            return 0
        C = sorted(C.items(), reverse=1)
        mx = C[0][0]
        add = C[0][1] - 1
        vacant = 0
        for i, (k, v) in enumerate(C[1:], 1):
            k2, _ = C[i-1]
            vacant += k2 - k - 1
            vacant -= v - 1
            if vacant < 0:
                add += abs(vacant)
                vacant = 0
        return mx + add

    return rec(src, -1)

N = INT()
nodes = [[] for i in range(N)]
for a in range(1, N):
    b = INT()
    b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

print(dfs(N, nodes, 0))
### BUGGY CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict

N, M = inpl()
Edge = defaultdict(lambda: [])
Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
par = list(Par)[0]
dist = [0]*N
Q = deque([par])
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            Q.appendleft(en)
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)    
        

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline()
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict
N, M = inpl()
Edge = defaultdict(lambda: [])
Pcan = defaultdict(lambda: 0)

Par = set(range(N)) 
for _ in range(N-1+M):
    A, B = inpl()
    Par.discard(B-1)
    Edge[A-1].append(B-1)
    Pcan[B-1] += 1
par = list(Par)[0]
dist = [0]*N
Q = deque([par])

while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] < dist[st] + 1:
            dist[en] = dist[st] + 1
            if Pcan[en] == 1:
                Q.append(en)
            else:
                Pcan[en] -= 1
Ans = [0]*N
Q = deque([par]) 
while Q:
    st = Q.pop()
    for en in Edge[st]:
        if dist[en] == dist[st] + 1:
            Ans[en] = st+1
            Q.appendleft(en)
for i in Ans:
    print(i)
### BUGGY CODE ###

p = int(input())
a = list(map(int,input().split()))

b = []
for i in range(p):
    if a[i] ==  1:
        b.append(i)

ans = [0]*p

for i in range(p):
    ans[i] += (-sum(list(map(lambda x:(x**(p-1-i))%p,b))))%p 

ans[0] += -len(b)*(p-1) 
ans[0] %= p

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

ans = [0]*p

for i,j in enumerate(a):
    if j == 0:
        continue
    ans[0] -= p-1
    m = 1
    for k in range(p):
        ans[p-1-k] -= m
        ans[p-1-k] %= p
        m *= i
        m %= p

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

from itertools import combinations
p = 10**9+7
N = int(input())
S = input().strip()
C = {}
for i in range(N):
    if S[i] not in C:
        C[S[i]]=0
    C[S[i]] += 1
D = list(C.items())
n = len(D)
cnt = 0
for i in range(1,n+1):
    for x in combinations(range(n),i):
        prod = 1
        for j in x:
            prod = (prod*D[j][1])%p
        cnt = (cnt+prod)%p
print(cnt)

### FIXED CODE ###

p = 10**9+7
N = int(input())
S = input().strip()
C = {chr(i):[] for i in range(97,123)}
for i in range(N):
    C[S[i]].append(i)
cnt = 1
for j in range(97,123):
    cnt = (cnt*(1+len(C[chr(j)])))%p
print((cnt-1)%p)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,A=map(int,input().split())

l=list(map(int,input().split()))
l.sort()
ans=[]

def dfs(num,i,count):
    num+=l[i]
    count+=1
    if num==A*count and num!=0:
        ans.append("A")#ここ何とかすれば終わり
    if num>A*count:
        return
    if i==len(l)-1:
        pass
    else:
        dfs(num,i+1,count)
    num-=l[i]
    count-=1
    if i==len(l)-1:
        pass
    else:
        dfs(num,i+1,count)

dfs(0,0,0)
print(len(ans))


### FIXED CODE ###

# coding: utf-8
# Your code here!
N,A=map(int,input().split())

X=list(map(int,input().split()))

dp=[[0]*2501 for i in range(50)]

for x in X:
    for i in range(49)[::-1]:
        for index,item in enumerate(dp[i]):
            if item!=0:
                dp[i+1][index+x]+=dp[i][index]
    dp[0][x]+=1

ans=0
for i in range(50):
    ans+=dp[i][A*(i+1)]

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

n=int(input())
a=[int(j) for j in input().split()]
mod=10**9+7
m=len(bin(max(a)))-2
l=[[0,0] for i in range(m)]
for i in a:
    b=bin(i)[2:].rjust(m,"0")[::-1]
    for j in range(m):
        if b[j]=="0":
            l[j][0]+=1
        else:
            l[j][1]+=1

ans=0
for i in range(m):
    ans+=(2**i)*l[i][0]*l[i][1]
    ans=ans%mod
print(ans)







### FIXED CODE ###

n=int(input())
a=[int(j) for j in input().split()]
mod=10**9+7
m=len(bin(max(a)))-2
l=[[0,0] for i in range(m)]
for i in a:
    b=bin(i)[2:].rjust(m,"0")[::-1]
    for j in range(m):
        if b[j]=="0":
            l[j][0]+=1
        else:
            l[j][1]+=1

ans=0
for i in range(m):
    ans+=l[i][0]*l[i][1]*pow(2,i,mod)
    ans=ans%mod
print(ans)
### BUGGY CODE ###

def main():
    list = []
    N = int(input())
    for i in range(0, N):
        ss = input()
        s = "".join(sorted(ss))
        list.append(s)
    result = 0
    for j in range(0, N):
        for k in range(j + 1, N):
            if list[j] == list[k]:
                result += 1
    print(result)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    dict = {}
    result = 0
    for i in range(N):
        s = "".join(sorted(input()))
        if s in dict:
            result += dict[s]
            dict[s] = dict[s] + 1
        else:
            dict[s] = 1
    print(result)


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

n = int(input())
lis = [x for x in input().split()]

for i in range(n):
  if  lis.count(lis[i]) >= 2:
    print("NO")
    exit()

print("YES")

### FIXED CODE ###

n = int(input())
lis = [x for x in input().split()]
lis.sort()

for i in range(1, n):
  if lis[i-1] == lis[i]:
    print("NO")
    exit()
  
print("YES")
### BUGGY CODE ###

import re

def C():
    n = input()
    s = input()
    ss = ""
    for i in range(len(s)):
        if i != 0:
            if s[i] != s[i-1]:
                ss += s[i]
        else:
            ss += s[i]
    print(len(ss))

if __name__ == '__main__':
    C()
    

### FIXED CODE ###

import re

def C():
    n = input()
    s = input()
    ss = re.sub(r"(.)\1{1,}",r"\1",s)
    print(len(ss))

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

N = int(input())
L = [int(i) for i in input().split()]

L.sort()

ans = 0

for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if L[i] + L[j] <= L[k]:
        break
      else:
        ans += 1

print(ans)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = [int(i) for i in input().split()]

L.sort()

ans = 0

for i in range(N):
  for j in range(i+1,N):
    max_len = L[i] + L[j]
    ans += bisect_left(L,max_len) - j - 1

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

class BIT:
    """1-indexed BIT
    """

    def __init__(self, size: int):
        """サイズを指定して BIT を初期化します。
        """
        self.__size = size
        self.__bit = [0] * (self.__size+1)

    def add(self, idx: int, val: int):
        """位置 idx (1-indexed) に値 val をたす。
        :param idx: 値を追加したいインデックス
        :param val: 追加したい値
        """
        while idx <= self.__size:
            self.__bit[idx] += val
            idx += idx & (-idx)

    def sum(self, idx: int)->int:
        s = 0
        while idx > 0:
            s += self.__bit[idx]
            idx -= idx & (-idx)
        return s


def inversion(A: list) -> int:
    bit = BIT(max(A))
    s = 0
    for a in A:
        s += bit.sum(a)
        bit.add(a, 1)

    return s


def check2(A: list, x: int)->int:
    n = len(A)
    S = [0] * (n + 1)
    for i in range(n):
        if x <= A[i]:
            S[i + 1] = S[i] + 1
        else:
            S[i + 1] = S[i] - 1

    m = min(S)
    return inversion([s - (m - 1) for s in S])


def median_of_medians(N: int, A: list) -> int:
    def check(x: int)->int:
        # S = [0] * (N + 1)
        # for i in range(N):
        #     if x <= A[i]:
        #         S[i + 1] = S[i] + 1
        #     else:
        #         S[i + 1] = S[i] - 1

        # m = min(S)
        # for i in range(N + 1):
        #     S[i] -= m - 1

        # bit = BIT(max(S))
        bit = BIT(2 * N + 1)
        s = 0
        a = 0
        for i in range(N):
            s += bit.sum(a + N)
            bit.add(a + N, 1)
            a = a + (1 if x <= A[i] else - 1)
            
        s += bit.sum(a + N)

        return s

    alpha = sorted(A)
    l, r = 0, N
    while r - l > 1:
        m = (r + l + 1) // 2
        if 2*check(alpha[m]) >= (N * (N + 1)) // 2:
            l = m
            if m == N - 1:
                break
            if 2 * check(alpha[m + 1]) < (N * (N + 1)) // 2:
                break
        else:
            r = m

    return alpha[l]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)


### FIXED CODE ###


def median_of_medians(N: int, A: list)->int:
    def search(c):
        bar = N
        r = 0
        res_nega = 0
        dp_arr = [0]*(2*N+1)
        for i in range(N):
            dp_arr[bar] += 1
            if A[i] < c:
                r += dp_arr[bar]
                bar += 1
            else:
                r -= (dp_arr[bar-1])
                bar -= 1
            res_nega += r
        return res_nega

    # binary search
    a_sorted = sorted(A)
    left = 0
    right = N
    mid = N // 2
    C = N*(N+1) // 2
    while True:
        if search(a_sorted[mid]) <= C // 2:
            if mid == N-1:
                break
            elif search(a_sorted[mid+1]) > C // 2:
                break
            else:
                left = mid
                mid = (mid + right) // 2
        else:
            right = mid + 1
            mid = (mid + left) // 2

    return a_sorted[mid]


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)
### BUGGY CODE ###

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


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.b[r - 1])
            if l & 1:
                s = self.func(s, self.b[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return s


c = [int(i) for i in input().split()]
seg = SegmentTree([{i} for i in c], lambda x, y: x | y, set())
for _ in range(q):
    l, r = [int(i) for i in input().split()]
    print(len(seg.get_segment(l-1, r)))

### FIXED CODE ###

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, a):
        self.n = len(a)
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.a[i] + x
            i += i & (-i)

    def get(self, i):
        s = 0
        i += 1
        while i != 0:
            s = s + self.a[i]
            i -= i & (-i)
        return s


def inmin(x):
    return int(x)-1


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(inmin, input().split()))
    que = [[i, list(map(inmin, input().split()))] for i in range(q)]
    que.sort(key=lambda x: x[1][1])
    ans = [0] * q

    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            ans[que[j][0]] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    print(*ans)