/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
ポエムオンラインジャッジ (Poem Online Judge, 以下 POJ と表記) は提出された文字列に得点をつけるオンラインジャッジです。
POJ に N 回の提出がありました。早い方から i 番目の提出では文字列 S_i が提出されて、得点は T_i でした。(同じ文字列が複数回提出される場合もあります)
ただし、POJ では 同じ文字列を提出しても得点が等しいとは限らない のに注意してください。
N 回の提出のうち、その提出よりも早い提出であって文字列が一致するものが存在しないような提出を オリジナル であると呼びます。
また、オリジナルな提出の中で最も得点が高いものを 最優秀賞 と呼びます。ただし、そのような提出が複数ある場合は、最も提出が早いものを最優秀賞とします。
最優秀賞は早い方から何番目の提出ですか？
制約
- 1 \leq N \leq 10^5
- S_i は英小文字からなる文字列
- S_i の長さは 1 以上 10 以下
- 0 \leq T_i \leq 10^9
- N, T_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N S_1 T_1 S_2 T_2 \vdots S_N T_N
出力
答えを出力せよ。
入力例 1
3 aaa 10 bbb 20 aaa 30
出力例 1
2
以下では早い方から i 番目の提出を提出 i と呼びます。
オリジナルな提出は提出 1 と 提出 2 です。提出 3 は提出 1 と文字列が一致しているためオリジナルではありません。
オリジナルな提出のうち最も得点が高い提出は提出 2 です。よってこれが最優秀賞になります。
入力例 2
5 aaa 9 bbb 10 ccc 10 ddd 10 bbb 11
出力例 2
2
オリジナルな提出は提出 1・提出 2・提出 3・提出 4 です。
その中で最も得点が高い提出は提出 2・提出 3・提出 4 です。この場合はこの中でもっとも提出の早い提出 2 を最優秀賞とします。
このように、オリジナルな提出の中で最も得点が高い提出が複数ある場合は、さらにその中で最も提出が早いものを最優秀賞とするのに注意してください。
入力例 3
10 bb 3 ba 1 aa 4 bb 1 ba 5 aa 9 aa 2 ab 6 bb 5 ab 3
出力例 3
8
Score : 300 points
Problem Statement
Poem Online Judge (POJ) is an online judge that gives scores to submitted strings.
There were N submissions to POJ. In the i-th earliest submission, string S_i was submitted, and a score of T_i 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 10^5
- S_i is a string consisting of lowercase English characters.
- S_i has a length between 1 and 10, inclusive.
- 0 \leq T_i \leq 10^9
- N and T_i are integers.
Input
Input is given from Standard Input in the following format:
N S_1 T_1 S_2 T_2 \vdots S_N T_N
Output
Print the answer.
Sample Input 1
3 aaa 10 bbb 20 aaa 30
Sample Output 1
2
We will refer to the i-th earliest submission as Submission i.
Original submissions are Submissions 1 and 2. Submission 3 is not original because it has the same string as that in Submission 1.
Among the original submissions, Submission 2 has the highest score. Therefore, this is the best submission.
Sample Input 2
5 aaa 9 bbb 10 ccc 10 ddd 10 bbb 11
Sample Output 2
2
Original submissions are Submissions 1, 2, 3, and 4.
Among them, Submissions 2, 3, and 4 have the highest scores. In this case, the earliest submission among them, Submission 2, is the best.
As in this sample, beware that if multiple original submissions have the highest scores, only the one with the earliest among them is considered the best submission.
Sample Input 3
10 bb 3 ba 1 aa 4 bb 1 ba 5 aa 9 aa 2 ab 6 bb 5 ab 3
Sample Output 3
8