Nightmare-a-thon

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 5.0s
Memory limit: 128M

Authors:
Problem types
Final Preparation!

You were 9 episodes into Date a Live when you noticed that something was wrong. Who is this Kurumi character and how come she is licking the protagonist's face? That is when you realize you were watching Date a Live 2 the entire time. Now you need to go through the difficult ordeal of marathoning Date a Live through the night! Unfortunately, you cannot live without food through the entire night, and the anime streamer you are using still does not have a pause button. This means out of the N total episodes, you need to skip some continuous episodes to go downstairs and eat something. Luckily, you have the overall ratings for the episodes, out of 10! The i^{th} episode has a user rating of k_{i}. In order to determine the best time to go make food, you have Q queries — each query asking the highest episode rating you can watch if you skip episodes a to b (inclusive) and how many episodes with this rating there are. It is guaranteed for any query, there will be at least one episode that you do not skip.

Input Specification

Line 1: two integers space separated, N,Q.

Line 2: N spaced integers, holding the rating for each episode, from 1 to 10.

The next Q lines will contain integers a and b (1 \le a \le b \le N).

Output Specification

For each query, output two integers space separated. The first integer should be the highest rated episode that isn't skipped, and the second integer should be the number of episodes with this rating.

Constraints

30% of cases

 1 \le N, Q \le  1\,000

100% of cases

 1 \le N, Q \le  500\,000

Sample Input

7 2
5 4 5 2 3 1 5
2 4
1 6

Sample Output

5 2
5 1

Explanation of Output for Sample Input

For the first query, episodes 2 to 4 will be skipped, leaving you with episode ratings: 5 x x x 3 1 5. The highest rated episode is 5, and both episodes 1 and 7 have this rating.


Comments


  • 4
    4fecta  commented on Aug. 11, 2019, 5:55 p.m.

    Given that the maximum rating of an episode is 3628800 (10!), those episodes must have been trash.


  • 1
    Dormi  commented on Aug. 29, 2017, 6:31 p.m.

    UMM in, "The first integer should be the highest rated episode that isn't skipped, and the second integer should be the number of episodes with this rating." and "The highest rated episode is 5, and both episodes 1 and 7 have this rating." You say "the highest rated episode" meaning you're asking for the episode which has the highest rating and not the highest episode rating.


  • 10
    BMP  commented on May 4, 2015, 10:15 p.m.

    One day..my keyboard will fly out the window.


    • 16
      kobortor  commented on May 5, 2015, 8:50 a.m.

      And you along with it.


      • 13
        BMP  commented on May 5, 2015, 9:38 a.m.

        do you wanna die


        • 8
          kobortor  commented on May 5, 2015, 10:13 a.m.

          Do you want to solve sketchly park?


          • 2
            Pleedoh  commented on July 31, 2017, 10:43 p.m.

            that's a fun one