A Simple Game

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Java 8 1.6s
PyPy 2 1.6s
PyPy 3 1.6s
V8 JavaScript 1.6s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

James and Edward are playing a game! They lay out N cards in a straight line, and chooses a breaking point. James chooses a card on the left side of the breaking point, and Edward chooses a card on the right side of the breaking point. Then they compare their card values to see whose card value is greater.

However, since Edward is just too good due to his massive brain, James has decided that Jessica will choose the breaking point, and they will see who is faster at choosing the maximum element on their respective side. Also, just for insurance, he has asked you to make a program that will tell him which card he and Edward will choose, help James!

Note: Both Edward and James may not choose the breaking point as their chosen card. In addition, if there are ties, break them by choosing the card with index that is the f-most side, where f is equal to left for James and right for Edward.

Input Specification

First line, two integers N and Q, denoting the number of cards and the number of times Jessica chooses a breaking point respectively.

Second line, N space separated integers a_i, denoting the value of each card.

Next Q lines, one integer x, specifiying the index of the breaking point.

Output Specification

For each query, output 2 space separated integers, the index of the card that James and Edward will choose respectively, given that they both will try their best to win.

Subtasks

For all subtasks

5 \le N \le 10^6

1 \le Q \le 10^6

2 \le x \le N - 1

-10^9 \le a_i \le 10^9

Subtask 1 [30%]

5 \le N \le 10^3

1 \le Q \le 10^3

Subtask 2 [70%]

No further constraints.

Sample Input 1

5 2
1 2 3 4 -5
3
4

Sample Output 1

2 4
3 5

Sample Explanation 1

For the first query, Jessica chooses index 3 as the breaking point, meaning the maximum element on the left side of the breaking point is 2 with index 2, and the right side is 4 with index 4.

For the second query, Jessica chooses index 4 as the breaking point, meaning the maximum element on the left side of the breaking point is 3 with index 3, and the right side is -5 with index 5.

Sample Input 2

5 2
2 2 2 6 6
3
4

Sample Output 2

1 5
1 5

Sample Explanation 2

For the first query, a_1 and a_2 both have the maximum value, however, for James, a_1 is closer to the left side of the array. Similarly, a_4 and a_5 both have the maximum value, but for Edward, a_5 is closer to the right side of the array.

The second query is a similar case.


Comments

There are no comments at the moment.