The Secret Garden of Numbers
Time Limit: 2.5 s
Memory Limit: 256.0 MB
Description
In a serene kingdom hidden among lush hills, there lies a secret garden filled with extraordinary plants, each represented by an integer in an enchanted array A of size N. This garden is watched over by a wise old gardener who has devised a series of mystical quests for curious adventurers eager to unlock its secrets.
Each adventurer must navigate through the garden by answering Q queries, each defined by a pair of integers l and r that indicate a specific range of plants to investigate. Their task is to find the minimum integer X within the specified range [l, r] that appears with a frequency greater than (r - l + 1) / 3. This means X should not only be a contender but must also flourish more abundantly than one-third of the total plants in that range, ensuring it is the minimal integer meeting the condition.
However, if the adventurers search thoroughly and find no integer that meets this requirement, they must humbly report their failure with a declaration of -1, indicating that the sought-after plant remains elusive.
Input
The first line contains two integers: N(size of the array) and Q(number of query) (1 <= N , Q <= \(2 * 10^5\)).
The second line contains N integers \(A_1\) , \(A_2\) ,,, \(A_N\) (1 ≤ \(A_i\) ≤ N), where \(A_i\) represents the various plants in the garden.
The next Q lines each contain two integers l and r (1 <= l <= r <= N), defining the range for each query.
Output
For each query, provide the minimum integer X that appears with a frequency greater than (r - l + 1) / 3, or -1 if no such integer exists.
Sample
Input | Output |
---|---|
|
|
Information
- ID
- 1103
- Difficulty
- 8
- Category
- Data_Structure | Math | Probability , Divide_and_Conquer Click to Show
- Tags
- # Submissions
- 171
- Accepted
- 16
- Accepted Ratio
- 9%
- Uploaded By
Related
In following contests: