Mock CCC '22 1 S4 - Berkeley Math Tournament Statistics

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$ ~N~ students numbered from $1$ ~1~ to $N$ ~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$ ~Q~ questions. Each question takes the form: Among all students from $L_i$ ~L_i~ to $R_i$ ~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 N, Q \le 10^5~

$1 \le s_i \le N$ ~1 \le s_i \le N~

$1 \le L_i \le R_i \le N$ ~1 \le L_i \le R_i \le N~

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

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

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

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

Input Specification

The first line contains two integers, $N$ ~N~ and $Q$ ~Q~.

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

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

Output Specification

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

Sample Input

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++.