102512: [AtCoder]ABC251 C - Poem Online Judge

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

问题描述

Poem Online Judge（POJ）是一个对提交的字符串进行评分的在线评测系统。
POJ共收到了$N$份提交。在第$i$次最早的提交中，提交了字符串$S_i$，并得到了$T_i$的分数。 （相同的字符串可能会被多次提交。）
请注意，POJ 不一定会给具有相同字符串的提交相同的分数。

如果提交中的字符串从未在任何更早的提交中提交，则称该提交为 原创 提交。
如果提交是原创提交，并且具有最高分数，则称该提交为 最佳 提交。如果有多个这样的提交，则仅考虑最早的提交为最佳提交。

找出最佳提交的索引。

约束条件

• $1 \leq N \leq 10^5$
• $S_i$ 是由小写英文字母组成的字符串。
• $S_i$ 的长度在$1$到$10$之间，包括$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$，是最好的。
如本示例所示，如果多