COCI 2020/2021 - Contest 6 - Index

View as PDF
Submit solution
Points: 1.50 (partial)
Time limit: 2.5s
Memory limit: 512M
Input: stdin
Output: stdout
Suggester:
tnbui
Problem source:
COCI 2020/2021 - Contest 6
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Chỉ số H (h-index) là chỉ số đánh giá dựa trên năng suất và số trích dẫn các bài báo của các học giả và nhà nghiên cứu. Chỉ số H được định nghĩa là giá trị ~H~ lớn nhất sao cho tác giả ấy có ít nhất ~H~ bài báo, mà mỗi bài được trích dẫn ít nhất ~H~ lần.

Giáo sư Mirko sắp nghỉ hưu. Suốt sự nghiệp, ông đã đăng ~N~ bài báo đánh số từ ~1~ đến ~N~. Ông tự hỏi rằng: giả như ông chỉ đăng các bài báo từ ~L~ đến ~R~ thì chỉ số H của ông sẽ là bao nhiêu?

Hãy giúp giáo sư trả lời câu hỏi trên ~Q~ lần.

Input

  • Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~ (~N, Q \leq 200000~).
  • Dòng tiếp theo chứa ~N~ số nguyên dương ~P_i~ (~P_i \leq 200000~) là số trích dẫn của bài báo thứ ~i~.
  • ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L~ và ~R~ (~1 \leq L \leq R \leq N~) cho câu hỏi của giáo sư Mirko.

Output

In ra ~Q~ dòng, mỗi dòng là đáp án cho câu hỏi của giáo sư với hai tham số tương ứng.

Ví dụ

Sample input
7 6
3 2 3 1 1 4 7
3 4
1 7
1 6
4 5
1 2
5 7
Sample output
1
3
3
1
2
2

Subtask

  1. ~N, Q \leq 1000~ (10 test)
  2. ~N, Q \leq 50000~ (10 test)
  3. Không có giới hạn gì thêm (10 test)

Comments

Please read the guidelines before commenting.


  • -13
    chunguyen2k8  commented on Aug. 7, 2024, 8:36 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -10
    l4adeveloper_main  commented on July 6, 2023, 12:03 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.