Mock CCC '22 1 S4 - Berkeley Math Tournament Statistics

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 0.25s
Memory limit: 32M

Problem type

Kaity is collecting statistics for the latest iteration of the Berkeley Math Tournament. In the last tournament, she had N students numbered from 1 to N participating. Each student received a score that was a positive integer number of points.

One day, Sylvia, her archnemesis, wanted to collect statistics about how well students did in the tournament. Sylvia has Q questions. Each question takes the form: Among all students from L_i to R_i, what was the most frequent score among the given students?

Kaity is a nice person and wants the students to look as good as possible, so if multiple scores are tied for most frequent, she will tell Sylvia the largest mode.

Sylvia is impatient, so please answer her questions as quickly as possible!

Constraints

1 \le N, Q \le 10^5

1 \le s_i \le N

1 \le L_i \le R_i \le N

In tests worth 1 mark, N, Q \le 10^3.

In tests worth an additional 2 marks, N, Q \le 10^4.

In tests worth an additional 3 marks, N, Q \le 2 \cdot 10^4.

In tests worth an additional 4 marks, N, Q \le 5 \cdot 10^4.

Input Specification

The first line contains two integers, N and Q.

The next line contains N integers, the scores s_i of the students from 1 to N in order.

The next Q lines contain two integers each, L_i and R_i, indicating the set of students Sylvia is asking about.

Output Specification

Output Q lines. On line i, output the answer to Sylvia's ith question.

Sample Input

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

Sample Output

2
2
1

Comments


  • 1
    Puddle  commented on April 26, 2022, 12:44 p.m. edited

    Is it even possible to solve this problem in Python 3 or Pypy3? (not asking for the solution, but all the correct answers have been in C++)


    • 1
      xiaowuc1  commented on April 26, 2022, 6:10 p.m.

      The only languages where this problem is expected to be solvable are C and C++.