X 만들기 (Hard)

이 문제는 X 만들기 문제와 $N$의 제한을 제외하고 같은 문제이다.

게시판에 $N$개의 압정이 꽂혀 있다. 압정은 매우 작은 크기의 점이고, 게시판은 무한한 크기의 좌표평면으로 표현된다. 알파벳 X를 좋아하는 포닉스는 꽂힌 압정들 중 몇 개를 제거해서 남은 압정들이 X자 모양을 이루게 하려고 한다. X자 모양의 정의는 다음과 같다.

• 압정들 중 중심이 되는 압정 $P$가 존재하고, 아래 조건을 만족한다.
• $P$와 같은 $x$좌표 또는 $y$좌표를 가지는 압정이 존재하지 않는다.
• $P$를 원점으로 생각했을 때, 한 사분면에 같은 $x$좌표 또는 $y$좌표를 가지는 압정 쌍이 존재하지 않으며 각 사분면에 압정이 하나 이상 있어야 한다.
• $P$를 원점으로 생각했을 때, 제1사분면과 제3사분면에 있는 압정들을 $x$좌표 순으로 정렬하면 정렬된 압정들의 $y$좌표는 증가한다.
• $P$를 원점으로 생각했을 때, 제2사분면과 제4사분면에 있는 압정들을 $x$좌표 순으로 정렬하면 정렬된 압정들의 $y$좌표는 감소한다.

포닉스를 위해 압정들의 위치가 주어질 때, 남은 압정들이 X자 모양을 이루도록 제거해야 하는 압정의 최소 개수를 구해 보자.

첫째 줄에 압정의 개수 $N$이 주어진다. ($1 \leq N \leq 100\,000$)

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 압정의 위치 $x_i$, $y_i$가 주어진다. ($-10^9 \leq x_i, y_i \leq 10^9$)

주어지는 좌표는 모두 정수이며, 같은 좌표를 가진 압정 쌍이 존재하지 않음이 보장된다.

남은 압정들이 X자 모양을 이루도록 제거해야 하는 압정의 최소 개수를 출력한다. 주어진 압정들로 X자 모양을 만들 수 없는 경우 -1을 출력한다.