18866번 - 젊은 날의 생이여

욱제는 입대를 앞두고 <이등병의 편지>를 부르고 있다.

… 이제 다시 시작이다 젊은 날의 생이여 … 

그런데 과연 욱제에게 젊은 날이 있었을까? 욱제에게 젊은 날이 있었는지 알아보자.

먼저, N년간 욱제의 행복도와 피로도가 주어진다. 행복도와 피로도는 양의 실수 값을 가진다. 어떤 1 ≤ K < N에 대해 1, 2, …, K년은 욱제의 젊은 날이고, K + 1, K + 2, …, N년은 욱제의 늙은 날이다.

젊은 날과 늙은 날은 다음의 조건을 만족한다:

• 임의의 젊은 날의 행복도는 임의의 늙은 날의 행복도보다 높다.
• 임의의 젊은 날의 피로도는 임의의 늙은 날의 피로도보다 낮다.

욱제는 자신의 행복도와 피로도를 이용하여 자신의 젊은 날을 알아보려 한다. 하지만, 일부 값이 누락되었다. 욱제를 도와주자.

첫째 줄에 N이 주어진다.

둘째 줄부터 N개의 줄에는 두 정수 u_i, v_i (1 ≤ i ≤ N)가 주어진다. u_i, v_i가 1 이상일 경우 각각 i년의 행복도와 피로도를 나타내며, 0인 경우에는 값이 누락되었음을 의미한다.

욱제의 젊은 날이 될 수 있는 최대 기간, 즉 문제의 조건을 만족할 수 있는 최대의 1 ≤ K < N을 출력한다. 단, 이러한 K가 없을 경우, -1을 출력한다.

• 2 ≤ N ≤ 1,000,000
• 0 ≤ u_i, v_i ≤ 10⁹
• 주어지는 N개의 행복도 중 0이 아닌 값은 모두 다르다.
• 주어지는 N개의 피로도 중 0이 아닌 값은 모두 다르다.