O Life of My Youth

Time limit2sMemory limit1024 MB

Summary

Given N pairs of happiness and fatigue with some values missing (0), find the largest K < N such that all young-day pairs can exceed all old-day pairs in happiness and stay below them in fatigue.

Level: Hard8 of 10
Topics: Sorting, Greedy, Implementation, Math
Solved: No attempts yet

Problem

Wookjae is singing right before his enlistment.

… Now it begins again, O life of my youth …

But did Wookjae ever have a youth? Let us find out whether Wookjae had a youth.

First, Wookjae's happiness and fatigue over N years are given. Happiness and fatigue take positive real values. For some 1 ≤ K < N, years 1, 2, …, K are Wookjae's young days, and years K + 1, K + 2, …, N are his old days.

The young days and the old days satisfy the following conditions:

The happiness of any young day is higher than the happiness of any old day.
The fatigue of any young day is lower than the fatigue of any old day.

Wookjae wants to determine his young days from his happiness and fatigue. However, some values are missing. Help Wookjae.

Input

The first line gives N.

Each of the next N lines gives two integers ui, vi (1 ≤ i ≤ N). If ui and vi are at least 1, they are the happiness and fatigue of year i, and if either is 0, that value is missing.

Output

Print the maximum length of Wookjae's young days, that is, the largest 1 ≤ K < N for which the conditions can hold. If no such K exists, print -1.

Constraints

2 ≤ N ≤ 1,000,000
0 ≤ ui, vi ≤ 109
Among the N given happiness values, all nonzero values are distinct.
Among the N given fatigue values, all nonzero values are distinct.

Examples3

Example 1
Input
```
5
5 1
4 2
3 3
2 5
1 4
```
Expected output
```
3
```
Example 2
Input
```
3
1 1
2 2
3 3
```
Expected output
```
-1
```
Example 3
Input
```
3
0 0
0 0
0 0
```
Expected output
```
2
```