CSES - Distinct Values Queries | Truy vấn Giá trị Khác nhau

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, Perl, PHP, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Swift
Điểm: 1800 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho một mảng gồm \(n\) số nguyên và \(q\) truy vấn có dạng: có bao nhiêu giá trị khác nhau trong đoạn \([a,b]\)?

Input

Dòng đầu tiên chứa hai số nguyên \(n\)\(q\) : kích thước mảng và số lượng truy vấn.

Dòng tiếp theo chứa \(n\) số nguyên \(x_1,x_2,...,x_n\): các giá trị của mảng.

Cuối cùng là \(q\) dòng mô tả các truy vấn. Mỗi dòng chứa hai số nguyên \(a\)\(b\).

Output

Với mỗi truy vấn, in ra số lượng giá trị khác nhau trong đoạn.

Giới hạn

  • \(1 \le n,q \le 2 \cdot 10^5\)
  • \(1 \le x_i \le 10^9\)
  • \(1 \le a \le b \le n\)

Ví dụ

Input

5 3
3 2 3 1 2
1 3
2 4
1 5

Output

2
3
3

Bình luận

Không có bình luận nào.