Description
There are N energy emission stations arranged in a line, each with a unique height Hi and the ability to emit energy value Vi simultaneously to both sides. The emitted energy is only received by the nearest taller station on each side.
Please calculate which station receives the most energy and the total amount of energy it receives.
(Figure 1: Height for Sample Test)
The total energy received by each station for Sample Test is: 5 0 7 7
If you use C++, you can add ios::sync_with_stdio(0); and cin.tie(0); to speed up input.
In quiz2, you can use std library
Input
The first line contains an integer N.
From the second to the N+1-th line, the i+1-th line contains two integers Hi and Vi, which represent the height and emitted energy value of the i-th emission station.
Subtask 1, 2: 1 <= N <= 5000, 1 <= Hi <= 105 , 1 <= Vi <= 105
Subtask 3, 4: 1 <= N <= 105
Subtask 5, 6: 1 <= N <= 5*106
For others Hi and Vi in Subtask 3,4,5,6 : 1 <= Hi <= 2*109, 1 <= Vi <= 109
(For subtasks 5 and 6, the time limit is 2 seconds.)
Output
Output two numbers that represent the station number that receives the most energy and the total amount of energy received.
If there are multi stations have same received energy, print the lower number one.