붐힐 마을 경비 활동

붐힐 마을 주변 바다에서 배찌와 다오 친구들은 불법 물풍선 투척, 아이템 밀수, 무단 맵 침입 등을 감시하기 위해 해안선 경비대를 꾸렸다. 해안선 경비대는 바다의 가상 수평선 위의 특정 위치에 물풍선을 설치하고 정박하며 해안선을 감시한다.

해안선은 꺾은선 $S$로 표현할 수 있는데, 꺾은선이란 $x$좌표가 오름차순으로 정렬된 평면상의 점 $p_1, p_2, \cdots, p_N$에 대해, 인접한 두 점 $p_i$와 $p_{i+1}$을 선분으로 이은 선분들의 집합을 의미한다. 편의상, 이 $N$ 개의 점을 꺾은선 $S$의 꼭짓점이라고 하자.

평면상에 수평선분 $L$이 존재하며, 해안선 경비대원은 수평선분 $L$ 위의 한 점으로 나타낼 수 있다. 이때, 수평선분 $L$의 양 끝점의 $x$좌표는 $p_1$과 $p_N$의 $x$좌표와 일치한다. 또한, 수평선분 $L$의 $y$좌표는 $0$이며, 꺾은선 $S$의 모든 꼭짓점의 $y$좌표는 $0$보다 크다.

꺾은선 $S$의 꼭짓점은 해안선의 변화점으로, 불법 활동이 발생하기 쉬운 지점이므로 해안선 경비대의 각별한 주의와 감시가 필요하다. 따라서, 수평선분 $L$ 위에 적절히 해안선 경비대원을 배치하여 모든 꼭짓점을 감시할 수 있어야 한다. 수평선분 $L$ 위의 해안선 경비대원이 꺾은선 $S$의 꼭짓점을 감시할 수 있으려면, 해안선 경비대원을 나타내는 점과 꼭짓점을 잇는 선분이 양 끝점을 제외하고 꺾은선 $S$와 만나서는 안 된다.

왼쪽 그림은 해안선을 표현하는 꺾은선 $S$와 해안선 경비대원이 위치할 수 있는 수평선분 $L$을 나타낸 것이다. 오른쪽 그림에서, $p$ 위치에 해안선 경비대원이 있을 때, $7$ 개의 꼭짓점을 감시할 수 있다. 마찬가지로, $q$ 위치에 해안선 경비대원이 있을 때도 $7$ 개의 꼭짓점을 감시할 수 있다. 감시할 수 있는 꼭짓점은 각각 빨간색 점선과 파란색 점선으로 연결되어 있다.

꺾은선 $S$의 모든 꼭짓점을 감시할 수 있는 최소 해안선 경비대원의 수를 구하는 프로그램을 작성하라.

입력 형식

첫 줄에 꺾은선 $S$의 꼭짓점의 수를 나타내는 정수 $N$이 주어진다. ($2 \le N \le 500\,000$)

이어지는 $N$ 개의 줄의 $i$ 번째 줄에는 꺾은선 $S$의 꼭짓점 $p_i$의 $x$좌표와 $y$좌표를 나타내는 두 정수 $x_i$와 $y_i$가 공백으로 구분되어 주어진다. ($0 \le x_i \le 1\,000\,000\,000;$ $1 \le y_i \le 1\,000\,000\,000;$ $x_1 = 0$)

$1$ 이상 $N-1$ 이하인 $i$에 대하여, $x_i < x_{i+1}$을 만족하고, $1$ 이상 $N-2$ 이하인 $i$에 대하여, $p_i$, $p_{i+1}$, $p_{i+2}$가 한 직선 위에 있지 않음이 보장된다.

출력 형식

첫 줄에 꺾은선 $S$의 모든 꼭짓점을 감시할 수 있는 최소 해안선 경비대원의 수를 출력한다.

예제

10
0 9
2 3
5 10
7 9
10 2
11 10
14 11
17 10
18 3
20 2

2

예제 설명

입력 예제의 상황은 본문의 그림과 같다. 그림에서 $p$ 위치와 $q$ 위치에 해안선 경비대원이 있으면, 꺾은선 $S$의 모든 꼭짓점을 감시할 수 있다. 한 명의 해안선 경비대원으로 모든 꼭짓점을 감시할 수는 없다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설