Make an X (Hard)

This problem is the same as Make an X except for the constraint on $N$.

$N$ pushpins are stuck on a board. Each pushpin is a very small point, and the board is modeled as an infinite coordinate plane. Phoenix, who likes the letter X, wants to remove some of the pushpins so that the remaining ones form an X shape. An X shape is defined as follows.

• There is a center pushpin $P$ that satisfies the conditions below.
• No other pushpin shares an $x$ coordinate or a $y$ coordinate with $P$.
• Treating $P$ as the origin, no two pushpins in the same quadrant share an $x$ coordinate or a $y$ coordinate, and each quadrant contains at least one pushpin.
• Treating $P$ as the origin, sort the pushpins in quadrants 1 and 3 by $x$ coordinate. Their $y$ coordinates increase.
• Treating $P$ as the origin, sort the pushpins in quadrants 2 and 4 by $x$ coordinate. Their $y$ coordinates decrease.

Given the positions of the pushpins, find the minimum number of pushpins to remove so that the remaining pushpins form an X shape.

The first line contains the number of pushpins $N$. ($1 \leq N \leq 100\,000$)

Each of the next $N$ lines contains the position $x_i$, $y_i$ of the $i$-th pushpin. ($-10^9 \leq x_i, y_i \leq 10^9$)

All coordinates are integers, and no two pushpins share the same coordinates.

Print the minimum number of pushpins to remove so that the remaining pushpins form an X shape. If the given pushpins cannot form an X shape, print -1.