Description
In the ruins of an ancient civilization, archaeologists have uncovered a row of $N$ Crystalline Spires — towering structures of varying heights. Each spire stores a reservoir of energy and, when activated, simultaneously broadcasts its energy value $V_i$ outward in both directions along the line.
However, due to the physical properties of crystalline resonance, the energy broadcast can only be absorbed by the nearest spire taller than itself on each side. If no taller spire exists on a given side, the energy dissipates into the void.
Please calculate which spire receives the most total energy and how much it receives.
Input
The first line contains an integer $N$.
From the 2nd to the $(N+1)$-th line, the $(i+1)$-th line contains two integers $H_i$ and $V_i$, representing the height and broadcast energy value of the $i$-th spire.
All $H_i$ are distinct.
Constraints
- Subtask 1, 2: $1 \le N \le 5000$, $1 \le H_i \le 10^5$, $1 \le V_i \le 10^5$
- Subtask 3, 4: $1 \le N \le 10^5$, $1 \le H_i \le 2\times10^9$, $1 \le V_i \le 10^9$
- Subtask 5, 6: $1 \le N \le 10^6$, $1 \le H_i \le 2\times10^9$, $1 \le V_i \le 10^9$
- Subtask 7, 8: $1 \le N \le 5\times10^6$, $1 \le H_i \le 2\times10^9$, $1 \le V_i \le 10^9$
(For subtasks 7 and 8, the time limit is 2 seconds.)
Output
Output two numbers: the station number that receives the most energy and the total amount of energy received.
If multiple stations receive the same maximum energy, print the one with the smaller index.