Jungle Outpost

There is a military base hidden deep in the jungle. It is surrounded by $n$ watchtowers equipped with ultrasonic generators. In this problem each watchtower is a point on the plane.

The watchtowers generate an ultrasonic field that protects every object lying strictly inside the convex hull of the towers. No tower lies strictly inside the convex hull, and no three towers are collinear.

The enemy can destroy some of the towers. When that happens, the protected area shrinks to the convex hull of the remaining towers.

The base commander wants to build the headquarters somewhere inside the protected area. To make it as safe as possible, he wants to maximize the number of towers the enemy must destroy in order to leave the headquarters unprotected.

The first line contains a single integer $n$ ($3 \le n \le 50,000$) — the number of watchtowers. Each of the next $n$ lines contains two integers, the Cartesian coordinates of one tower. Every coordinate does not exceed $10^6$ in absolute value. The towers are listed in the order in which their convex hull is traversed clockwise.

Print a single integer: the number of watchtowers the enemy must destroy to leave the headquarters unprotected, assuming the headquarters is placed optimally.