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

N = int(input())
H = list(map(int,input().split()))
ans =[] 
for i in range(N):
  move = 0
  for j in range(i,N-1):   
    if H[j] >= H[j+1]:
      move += 1
    else:
      break    
  ans.append(move)
print(max(ans))
  

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
ans=0
cnt=0
for i in range(1,n):
  if h[i]<=h[i-1]:
    cnt+=1
    if cnt>ans:
      ans=cnt
  else:
    cnt=0
print(ans)
### BUGGY CODE ###

import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    edges = dict()
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        if u - 1 in edges.keys():
            edges[u - 1].update({v - 1: w % 2})
        else:
            edges.update({u - 1: {v - 1: w % 2}})
        if v - 1 in edges.keys():
            edges[v - 1].update({u - 1: w % 2})
        else:
            edges.update({v - 1: {u - 1: w % 2}})
    return N, edges


def solve(N, edges):
    c = np.ones((N, ), dtype=np.int32) * -1  # -1: unvisited, 0: white, 1: black
    stack = list()
    c[0] = 0
    stack.append(0)
    while len(stack) > 0:
        s = stack.pop()
        for t in edges[s].keys():
            if c[t] == -1:
                if edges[s][t]:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                stack.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)


### FIXED CODE ###

import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    to = [[] for _ in range(N)]
    cost = [[] for _ in range(N)]
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        to[u-1].append(v-1)
        to[v-1].append(u-1)
        cost[u-1].append(w % 2)
        cost[v-1].append(w % 2)
    return N, to, cost


def solve(N, to, cost):
    c = [-1] * N  # -1: unvisited, 0: white, 1: black
    q = list()
    c[0] = 0
    q.append(0)
    while len(q) > 0:
        s = q.pop()
        for t, co in zip(to[s], cost[s]):
            if c[t] == -1:
                if co:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                q.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)
### BUGGY CODE ###

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

def get_prime(p):
  result = []
  if p==1:
    return result
  else:
    integers = [1 for _ in range(p+1)]
    integers[0] = 0
    integers[1] = 0
    for i in range(p+1):
      if integers[i] == 1:
        result.append(i)
        for j in range(i,p+1,i):
          integers[j] = 0
    return result

P = get_prime(10**6+1)
list_count = [0 for _ in range(len(P))]

for a in A:
  for i in range(len(P)):
    p = P[i]
    if a%p == 0:
      list_count[i] += 1
    if a < p:
      break

v = max(list_count)
if v == N:
  answer = 'not coprime'
elif v <= 1:
  answer = 'pairwise coprime'
else:
  answer = 'setwise coprime'

print(answer)

### FIXED CODE ###

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

def get_count(p):
  integers = [1 for _ in range(p+1)]
  integers[0] = 0
  integers[1] = 0
  counts = [0 for _ in range(p+1)]
  for a in A:
    counts[a] += 1
  answer = 0
  for i in range(p+1):
    if integers[i] >= 1:
      count = 0
      for j in range(i,p+1,i):
        count += counts[j]
        integers[j] = 0
      answer = max(answer,count)
  return answer

count = get_count(max(A))
if count == N:
  answer = 'not coprime'
elif count >= 2:
  answer = 'setwise coprime'
else:
  answer = 'pairwise coprime'

print(answer)
### BUGGY CODE ###

N = int(input())
L = []
for _ in range(N):
  L.append("".join(sorted(input())))
R = set(L)
c = 0
for r in R:
  t = L.count(r)
  c += t*(t-1)//2
print(c)

### FIXED CODE ###

from collections import Counter
N = int(input())
L = ["".join(sorted(input())) for _ in range(N)]
T = Counter(L).values()
print(sum(v*(v-1)//2 for v in T))
### BUGGY CODE ###

INF = 10000
n,k = map(int,input().split())
stair = list(map(int,input().split()))
dp = [""]*n
for i in range(n):
    dp[i] = list()

for i in range(0,n):
    for j in range(i+1,min(i+k+1,n)):
        if(i == 0):
            cost = abs(stair[i]-stair[j])
        else:
            cost = abs(stair[i]-stair[j]) + dp[i]
        
        try:
            dp[j] = min(cost,dp[j])
        except:
            dp[j] = cost
        # print(cost,i,j)



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

### FIXED CODE ###

INF = 10000
n,k = map(int,input().split())
stair = list(map(int,input().split()))
dp = [0] *n
for i in range(1,n):
    dp[i] = dp[i-1]+abs(stair[i]-stair[i-1])
    for j in range(1,k+1):
        if(i - j >= 0):
            # print(i,i-j)
            dp[i] = min(dp[i], dp[i-j]+abs(stair[i]-stair[i-j]))
        # print(dp)



print(dp[-1])
### BUGGY CODE ###

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

for i in range(N):
    del_num = X[i:i + 1]
    X.pop(i)
    list1 = sorted(X)
    print(list1[N // 2-1])
    X.insert(i, int(del_num[0]))

### FIXED CODE ###

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

for i in range(N):
    if list[int((N/2))]<=X[i]:
        print(list[int(N/2)-1])
    else:
        print(list[int(N/2)])
### BUGGY CODE ###

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

import sys

def isprime(n):
    for i in xrange(2, int(n**0.5)+1):
        if n % i == 0: return False
    return True

limit = 1000000
ansList = [0]*limit # 1 is not prime
cnt = 0
for i in xrange(2, limit):
    if isprime(i): cnt += 1
    ansList[i-1] = cnt

#for line in ["999999"]:
for line in sys.stdin.readlines():
    List = map(int, line.strip().split())

    n = List[0]
    print ansList[n-1]

### FIXED CODE ###

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

import sys

limit = 1000000

prime01List = [1]*limit
prime01List[0] = 0 # 1 is not prime
for i in xrange(2, int(limit**0.5)+1):
    n = 2*i
    while(n <= limit):
        prime01List[n-1] = 0
        n += i


ansList = [0]*limit
cnt = 0
for i in xrange(limit):
    cnt += prime01List[i]
    ansList[i] = cnt


#for line in ["999999"]:
for line in sys.stdin.readlines():
    List = map(int, line.strip().split())

    n = List[0]
    print ansList[n-1]
### BUGGY CODE ###

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

L=sorted(L)
counter=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]:counter+=1
print(counter)



### FIXED CODE ###

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

import bisect
L.sort()
ans = 0
bl = bisect.bisect_left
br = bisect.bisect_right
for i,a in enumerate(L):
    for j,b in enumerate(L[i+1:],i+1):
        m = b-a+1
        M = b+a-1
        ans += br(L,M,j+1) - bl(L,m,j+1)
print(ans)
### BUGGY CODE ###

N,W = map(int, input().split())
dp = [0] * (W + 1)
nupList = [map(int, input().split()) for _ in range(N)]

for w, v in nupList:
    for j in range(W, w - 1, -1 ):
        DP = dp[j - w] + v
        if dp[j] < DP:
            dp[j] = DP

print(dp[W])


### FIXED CODE ###

def DP():
    n,W = map(int, input().split(' '))
    WV = (map(int, input().split(' ')) for _ in range(n))
    dp = [0] * (W+1)
 
    for w, v in WV:
        for j in range(W, w-1, -1):
            DP = dp[j-w] + v
            if dp[j] < DP:
                dp[j] = DP
    return max(dp)
print(DP())
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
b = a.copy()

for i in range(1, n):
    if sum(a[:i]) >= 0 and sum(a[:i+1]) >= 0:
        a[i] = -1 - sum(a[:i])
    elif sum(a[:i]) <= 0 and sum(a[:i+1]) <= 0:
        a[i] = 1 - sum(a[:i])

print(sum(abs(b-a)))

### FIXED CODE ###

n=input()
a=[int(i) for i in input().split()]
def chk(a,t):
    ans=0
    x=0
    for i in a:
        x+=i
        if t==True and x<1:
            ans+=1-x
            x=1
        elif t==False and x>-1:
            ans+=x+1
            x=-1
        t=not t
    return ans
print(min(chk(a,True),chk(a,False)))
### BUGGY CODE ###

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for dx,dy in moves:
    for x,y in q:
      xx = x+dx
      yy = y+dy
      if not visited[xx][yy]:
        visited[xx][yy] = True
        qq.append((xx,yy))
  q = qq
  
print(ans)

### FIXED CODE ###

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###


class Node:
    def __init__(self, key=-1):
        self.key = key
        self.parent = -1
        self.left = -1
        self.right = -1
    
    def setKey(self, key):
        self.key = key


def insert(T_, z): #(T, Node)
    global T
    y = -1
    x = T_ #Node()
    while x != -1 :
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y == -1:
        T = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z


def preParse(T):
    if T == -1 and T == -1:
        return
    print T.key,
    preParse(T.left)
    preParse(T.right)

def inParse(T):
    if T == -1 and T == -1:
        return
    inParse(T.left) #Node() or -1
    print T.key,
    inParse(T.right)


T = -1

def main():
    com = []
    m = int(raw_input())
    for i in xrange(m):
        com.append(raw_input())
    for i in xrange(m):
        if com[i][0] == 'i':
            insert(T,Node(key=int(com[i][7:])))
        else:
            print '',
            inParse(T)
            print
            print '',
            preParse(T)
            print 
    return 0

main()
            

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
  
  
class Node(object):
    def __init__(self, key=None):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
  
  
def tree_insert(top, z):
    y = None
    x = top
    while isinstance(x, Node):
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        top = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z
    return top
  
  
def inorder_walk(node):
    if node.left:
        inorder_walk(node.left)
    print('', node.key, end='')
    if node.right:
        inorder_walk(node.right)
  
  
def preorder_walk(node):
    print('', node.key, end='')
    if node.left:
        preorder_walk(node.left)
    if node.right:
        preorder_walk(node.right)
  
  
n = int(stdin.readline())
  
top = None
for _ in range(n):
    cmd = stdin.readline()
    if cmd.startswith('i'):
        key = int(cmd[7:])
        #assert -2000000000 <= key <= 2000000000
        top = tree_insert(top, Node(key))
    else:
        inorder_walk(top)
        print()
        preorder_walk(top)
        print()
### BUGGY CODE ###

class unionfind():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.size = [1 for i in range(n)]

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

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x!=y:
            self.par[y] = x
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n,m,k = map(int,input().split())
uff = unionfind(n)
fr = [0 for i in range(n)]


for i in range(m):
    a,b = map(lambda x:int(x)-1,input().split())
    uff.unite(a,b)
    fr[a]+=1
    fr[b]+=1


ans = [uff.get_size(i) -fr[i]-1 for i in range(n)]

for i in range(k):
    c,d = map(lambda x:int(x)-1,input().split())
    if uff.same(c,d):
        ans[c] -=1
        ans[d] -=1

print(*ans)


### FIXED CODE ###


def main():
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        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 size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        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 group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n,m,k = map(int,input().split())
    uff = UnionFind(n)
    fr = [0]*n

    for i in range(m):
        a,b = map(int,input().split())
        uff.union(a-1,b-1)
        fr[a-1]+=1
        fr[b-1]+=1


    ans = [uff.size(i) -fr[i]-1 for i in range(n)]

    for i in range(k):
        c,d = map(int,input().split())
        if uff.same(c-1,d-1):
            ans[c-1] -=1
            ans[d-1] -=1
    print(*ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

import itertools

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]

answer = 0

nums=[]
for i in range(1, M+1):
    nums.append(i)

for balls in itertools.combinations_with_replacement(nums, N):
    score = 0
    for i in range(Q):
        test = list(balls)
        if test[abcd[i][0]-1] + abcd[i][2] == test[abcd[i][1]-1]:
            score += abcd[i][3]
    if score > answer:
        answer = score

print(answer)


### FIXED CODE ###

import itertools

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]

answer = 0

nums=[]
for i in range(1, M+1):
    nums.append(i)

for balls in itertools.combinations_with_replacement(nums, N):
    score = 0
    test = list(balls)
    for i in range(Q):
        if test[abcd[i][0]-1] + abcd[i][2] == test[abcd[i][1]-1]:
            score += abcd[i][3]
    if score > answer:
        answer = score

print(answer)
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
n,x,y = list(map(int, input().split()))

graph = []
for i in range(n):
    g1 = [0]*n
    if i-1 >= 0:
        g1[i-1] = 1
    if i+1 <= n-1:
        g1[i+1] = 1
    graph.append(g1)

graph[x-1][y-1] = 1
graph[y-1][x-1] = 1

graph = csr_matrix(graph)
dist_matrix= floyd_warshall(csgraph=graph, directed=False)

ans = [0]*(n)
for i in range(n):
    for j in range(i+1, n):
        ans[int(dist_matrix[i][j])] += 1

for i in ans[1:]:
    print(i)

### FIXED CODE ###

n,x,y = list(map(int, input().split()))

ans = [0]*(n)
for i in range(n-1):
    for j in range(i+1, n):
        r1 = min(j-i, (abs(x-i-1) + 1 +  abs(y-j-1) ), (abs(y-i-1) + 1 +  abs(x-j-1) ) )
        ans[r1] += 1

for i in ans[1:]:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
#print(S)
now='.'
ans=0
x,y=0,0
if S[x][y]=='#':
  ans+=1
  now='#'
  
def findroot(x,y,S,d,now,nextkouho):
  nextkouho.add((x,y))
  if x<H-1 and S[x+1][y]==now:
    nextkouho=findroot(x+1,y,S,d+1,now,nextkouho)
  if y<W-1 and S[x][y+1]==now:
    nextkouho=findroot(x,y+1,S,d+1,now,nextkouho)
  return nextkouho
kouho=[(0,0)]
#print(kouho)
while 1:
  nextkouho=set()
  for x,y in kouho:
    if x<H-1 and S[x+1][y]==now:
      nextkouho=findroot(x+1,y,S,0,now,nextkouho)
    else:
      nextkouho.add((x,y))
    if y<W-1 and S[x][y+1]==now:
      nextkouho=findroot(x,y+1,S,0,now,nextkouho)
    else:
      nextkouho.add((x,y))
  if (H-1,W-1) in nextkouho:
    break
  if now=='#':
    now='.'
  else:
    ans+=1
    now='#'
  kouho=list(nextkouho)
  #print(nextkouho,kouho,now,ans)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
dp=[0]*W
if S[0][0]=='#':
  dp[0]=1
for j in range(1,W):
  if S[0][j]!=S[0][j-1] and S[0][j-1]=='.':
    dp[j]=dp[j-1]+1
  else:
    dp[j]=dp[j-1]
for i in range(1,H):
  if S[i][0]!=S[i-1][0] and S[i-1][0]=='.':
    dp[0]=dp[0]+1
  for j in range(1,W):
    hidari=1 if S[i][j]!=S[i][j-1] and S[i][j-1]=='.' else 0
    ue=1 if S[i][j]!=S[i-1][j] and S[i-1][j]=='.' else 0
    dp[j]=min(dp[j-1]+hidari,dp[j]+ue)
print(dp[-1])
### BUGGY CODE ###

from collections import Counter

N = input()
A_str = input().split()

if "0" in A_str:
    print(0)
    exit()

c = Counter(sorted(A_str))
res = 1
for i, v in c.items():
    res *= int(i) ** v

if res > 10 ** 18:
    res = -1

print(res)


### FIXED CODE ###

N = input()
A_str = input().split()
A_array = map(int, A_str)

if "0" in A_str:
    print(0)
    exit()

res = 1
for A in A_array:
    res *= A
    if res > 10 ** 18:
        res = -1
        break

print(res)
### BUGGY CODE ###

from itertools import chain
# import numpy as np
# N = int(input())
# L,N = map(int,input().split())
# X = [list(map(int,input().split())) for x in range(N)]
K,S = map(int,input().split())
patterns = 0

arr = [[[x+y+z for z in range(min(S-x-y+1,K+1))] for y in range(min(S-x+1,K+1))] for x in range(K+1)]
farr = list(chain.from_iterable(arr))
farr = list(chain.from_iterable(farr))
# print(farr)
print(farr.count(S))
# print(patterns)

### FIXED CODE ###

K,S = map(int,input().split())
patterns = 0

# # arr = [[x+y for y in range(min(S-x+1,K+1))] for x in range(K+1)]
# farr = list(chain.from_iterable(arr))
# for z in farr:
#     temp_z = S - z
#     if temp_z <= K and temp_z >=0:
#         patterns += 1
# print(farr)
# print(farr.count(S))

for x in range(K+1):
    for y in range(max(0,S-K-x), min(K+1,S-x+1)):
        patterns += 1
print(patterns)
### BUGGY CODE ###

n = int(input())
Ls = list(map(int, input().split()))
cnt = 0


def check(a, b, c):
    if a < b+c and b < c + a and c < a + b:
        return True
    else:
        return False


for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if check(Ls[i], Ls[j], Ls[k]):
                cnt += 1
print(cnt)


### FIXED CODE ###

import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
from bisect import bisect_right
input = lambda: sys.stdin.readline().rstrip()


def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return


def main():
    n = int(input())
    Ls = list(map(int, input().split()))
    Ls.sort()
    cnt = 0
    for i in range(0,n-2):
        for j in range(i+1,n-1):
            #k以下なら良い
            k =  Ls[i] + Ls[j] -1
            # bisect_right(Ls, k)個の要素が左にある
            # 答え: bisect_right(Ls, k) - j
            cnt += max(bisect_right(Ls, k) - j-1, 0)
            # print(Ls, Ls[i],Ls[j],k, bisect_right(Ls,k)-j-1)
    print(cnt)
            

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

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

ans = 0
for i in range(n-k+1):
    e = 0
    for j in range(k):
        e += ((1+p[i+j])*p[i+j]/2)/p[i+j]
    ans = max(ans, e)
print(ans)

### FIXED CODE ###

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

# ans = 0
# for i in range(n-k+1):
#     e = 0
#     for j in range(k):
#         e += ((1+p[i+j])*p[i+j]/2)/p[i+j]
#     ans = max(ans, e)
# print(ans)

cum = [0]
for i in range(n):
    cum.append(cum[-1] + p[i])

mx = (0, 0)
for i in range(n-k+1):
    idx = i+k-1
    mx = max(mx, (cum[i+k]-cum[i], idx))

ans = 0
for i in range(k):
    ans += ((1+p[mx[1]-i])*p[mx[1]-i]/2)/p[mx[1]-i]
print(ans)
### BUGGY CODE ###

import sys
read=sys.stdin.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def update(x,i):
    if good[x]==-1:
        good[x]=i
        bit.add(i,1)
    else:
        bit.add(good[x],-1)
        good[x]=i
        bit.add(good[x],1)

N,Q=map(int,read().split())
c=list(map(int,read().split()))
Query=[list(map(lambda x:int(x)-1,read().split()))+[i] for i in range(Q)]
Query.sort(key=lambda x:x[1])
ans=[-1]*Q
good=[-1]*(N+1)
bit=BIT(N)


i=0
for L,R,w in Query:
    while(i<=R and i<N):
        update(c[i],i)
        i+=1
    ans[w]=bit.cum(L,R+1)

print(*ans,sep='\n')

### FIXED CODE ###

import sys
read=sys.stdin.buffer.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def main():
    def update(x,i):
        if good[x]==-1:
            good[x]=i
            bit.add(i,1)
        else:
            bit.add(good[x],-1)
            good[x]=i
            bit.add(good[x],1)
        return
    
    N,Q=map(int,read().split())
    c=tuple(map(int,read().split()))
    Query=[]
    for i in range(Q):
        l,r=map(lambda x:int(x)-1,read().split())
        Query.append((l,r,i))
    Query.sort(key=lambda x:x[1])
    ans=[-1]*Q
    good=[-1]*(N+1)
    bit=BIT(N)

    i=0
    for L,R,w in Query:
        while(i<=R):
            update(c[i],i)
            i+=1
        ans[w]=bit.cum(L,R+1)

    print(*ans,sep='\n')
    return
    
if __name__=='__main__':
    main()