Find the Diamond Box

Welcome to the "Grand Prize" game show! There are n boxes numbered from \(0\) to \(n-1\) arranged in a row, each containing a hidden prize. There are \(v \le 5\) types of prizes, ranked by value from \(1\) to \(v\) in descending order. Type \(1\) is a diamond — the most valuable prize — and it appears exactly once. For every type \(t\) with \(2 \le t \le v\), if there are \(k\) prizes of type \(t-1\), then there are strictly more than \(k^2\) prizes of type \(t\).

Your goal is to win the diamond. Before choosing one box to open at the end, you are allowed to ask the host a few questions. For any chosen box \(i\) (\(0 \le i < n\)), the host will respond with an array \(a = [a_0, a_1]\), where:

• \(a_0\) is the exact number of boxes to the left of box \(i\) that contain prizes more valuable than the prize in box \(i\),
• \(a_1\) is the exact number of boxes to the right of box \(i\) that contain prizes more valuable than the prize in box \(i\).

Notice that if you query the box that contains the diamond, its answer will be \([0, 0]\) since no prize is more valuable than the diamond. Your task is to determine, with as few queries as possible, which box contains the diamond.

Note: In this problem, you are given the responses for all boxes. You are to output the index of the box whose response is \([0, 0]\). It is guaranteed that there is exactly one such box.

inputFormat

The input begins with a single integer \(n\) representing the number of boxes. Following this, there are \(n\) lines, each containing two space-separated integers \(a_0\) and \(a_1\), representing the host's response for boxes \(0\) to \(n-1\) respectively.

Input Format:

n
 a_0 a_1
 a_0 a_1
 ... (n lines total)

outputFormat

Output a single integer, the 0-indexed position of the box that contains the diamond (i.e. the box whose response is \([0, 0]\)).

sample

5
0 1
0 1
0 0
1 0
1 0

2