B - Changing Trains Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

AtCoder 駅には 2 つの路線があり、片方は高橋駅ゆき、もう片方は青木駅ゆきです。

N 本の列車のデータが与えられます。 i 本目 (1\leq i\leq N) のデータは文字列と正整数の組 (S _ i,T _ i) で表されます。S _ i は Aoki もしくは Takahashi のどちらかと等しく、S _ i ゆきの列車が T _ i 分後に AtCoder 駅に到着することを表します。

あなたは、N 本のうち AtCoder 駅にもっとも早く到着する高橋駅ゆきの列車に乗ろうと思っています。 何本目の列車に乗ることになるか求めてください。

制約

  • 1\leq N\leq2\times10 ^ 5
  • S _ i は Aoki もしくは Takahashi のどちらかと等しい (1\leq i\leq N)
  • 1\leq T _ i\leq10 ^ 9\ (1\leq i\leq N)
  • i\neq j ならば T _ i\neq T _ j\ (1\leq i,j\leq N)
  • S _ i={}Takahashi であるような i が存在する
  • N および T _ i\ (1\leq i\leq N) はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
S _ 1 T _ 1
S _ 2 T _ 2
\vdots
S _ N T _ N

出力

答えを出力せよ。

入力例 1

5
Aoki 2
Takahashi 3
Takahashi 5
Aoki 10
Takahashi 15

出力例 1

2

AtCoder 駅に到着する 5 本の列車の情報が与えられています。 このうち、高橋駅ゆきの列車は 3 分後に到着する 2 本目の列車、5 分後に到着する 3 本目の列車、15 分後に到着する 5 本目の列車の 3 本です。

この中で最も到着が早い列車は 2 本目の列車なので、2 を出力してください。

入力例 2

8
Aoki 748
Aoki 436
Aoki 170
Aoki 587
Aoki 972
Aoki 331
Takahashi 532
Takahashi 523

出力例 2

8

到着する時刻がソートされて与えられるとは限らないことに注意してください。

Problem Statement

Trains from AtCoder station have two destinations: Takahashi station and Aoki station.

You are given information on N trains. The i-th train (1\leq i\leq N) is described by a pair (S _ i,T _ i) of a string and a positive integer. It means that the train for station S _ i arrives at AtCoder station T _ i minutes later, where S _ i is equal to either Aoki or Takahashi.

You are going to take the train for Takahashi station that arrives earliest at AtCoder station. Which train are you taking?

Constraints

  • 1\leq N\leq2\times10 ^ 5
  • S _ i is equal to either Aoki or Takahashi (1\leq i\leq N).
  • 1\leq T _ i\leq10 ^ 9\ (1\leq i\leq N)
  • If i\neq j, then T _ i\neq T _ j\ (1\leq i,j\leq N).
  • There exists i with S _ i={}Takahashi.
  • N and T _ i\ (1\leq i\leq N) are all integers.

Input

The 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

If he is taking the i-th train (1\leq i\leq N), print the integer i.

Sample Input 1

5
Aoki 2
Takahashi 3
Takahashi 5
Aoki 10
Takahashi 15

Sample Output 1

2

Information on five trains arriving at AtCoder station is given. Three of them are for Takahashi station: the 2-nd train arriving three minutes later, the 3-rd train arriving five minutes later, and the 5-th train arriving 15 minutes later.

The 2-nd train arrives earliest among them, so 2 should be printed.

Sample Input 2

8
Aoki 748
Aoki 436
Aoki 170
Aoki 587
Aoki 972
Aoki 331
Takahashi 532
Takahashi 523

Sample Output 2

8

Note that the given arrival times may not be sorted.