Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 300300 points
Problem Statement
Poem Online Judge (POJ) is an online judge that gives scores to submitted strings.
There were NN submissions to POJ. In the ii-th earliest submission, string S_iSi was submitted, and a score of T_iTi was given. (The same string may have been submitted multiple times.)
Note that POJ may not necessarily give the same score to submissions with the same string.
A submission is said to be an original submission if the string in the submission is never submitted in any earlier submission.
A submission is said to be the best submission if it is an original submission with the highest score. If there are multiple such submissions, only the earliest one is considered the best submission.
Find the index of the best submission.
Constraints
-
1 \leq N \leq 1000001≤N≤100000
-
S_iSi is a string consisting of lowercase English characters.
-
S_iSi has a length between 11 and 1010, inclusive.
-
0 \leq T_i \leq 10^90≤Ti≤109
-
NN and T_iTi are integers.
Input
Input is given from Standard Input in the following format:
NNS_1S1T_1T1S_2S2T_2T2\vdots⋮S_NSNT_NTN
Output
Print the answer.