Informatica Online Judge

  선천적 얼간이들 [2181 / 0885]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 0   Total Tried : 1


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (33rd 최지원)]

Background

호주까지가서 돈을 벌려던 카츠파트는 치즈공장에 취직했다가 과로사 직전에 그만두었다.

악덕사장 admin에 속아 koistudy에 입사(사실 노예 계약)한 카츠파트는, 수열에 쿼리를 처리하는 일을 하고있다.

하지만 오늘은 비가와서 카츠파트는 심신이 붕괴되어 사경을 헤매게 되었다!

불쌍한 카츠파트를 위해 쿼리를 대신 처리해 주자.

Input

첫째줄에 수열의 길이 $a$와 쿼리의 개수 $b$가 주어진다.

다음줄에 길이$a$의 수열 $X$가 주어진다.

이후 $b$줄에 걸쳐 정수 $2$개로 이루어진 쿼리 $C_i$ $D_i$가 출력된다.


[입력값의 정의역]

$1≤a,~b≤100000$
$1≤X_i≤1000000$
$1≤C_i≤D_i≤a$

Output

$b$줄에 걸쳐서 $X_{C_i}$~$X_{B_i}$ 사이의 서로다른 정수가 몇 종류 있는지 출력하시오

IO Example

입력
10 5
2 2 4 3 6 7 8 1 1 1
1 2
1 10
2 9
3 5
1 5

출력
2 2 //1~2번에서 가장 큰 수는 2이고, 2번 나온다
8 1 //1~10번에서 가장 큰 수는 8이고 1번 나온다
8 1
6 1
6 1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]