개선

손 할로에게는 1번부터 $n$번까지 번호가 붙은 우주선 $n$대와 우주 정거장 하나가 있다. 정거장과 우주선은 모두 한 직선 위에 있다. 우주선 $i$는 정거장에서 $x_i$미터 떨어져 있고, 모든 $x_i$가 양수이므로 우주선은 모두 정거장의 같은 쪽에 있다. $x_i$는 서로 다르다. 정거장의 번호는 0이고 $x_0 = 0$이다.

번호가 연속한 두 우주선은 밧줄로 이어져 있고, 첫 번째 우주선은 정거장과 이어져 있다. 밧줄 $i$($1 \le i \le n$)는 우주선 $i$와 우주선 $i-1$을 잇는다. 즉 밧줄 1은 첫 번째 우주선과 정거장을 잇는다.

$x_k^{\min} = \min(x_{k-1}, x_k)$, $x_k^{\max} = \max(x_{k-1}, x_k)$로 쓴다. 손 할로는 구간 $[x_i^{\min}, x_i^{\max}]$과 $[x_j^{\min}, x_j^{\max}]$이 내부의 점을 공유하고 어느 쪽도 다른 쪽을 완전히 포함하지 않을 때 밧줄 $i$와 밧줄 $j$가 교차한다고 본다. 다음 중 하나가 성립하는 경우다.

$\begin{cases} x_i^{\min} < x_j^{\min} < x_i^{\max} < x_j^{\max} \\ x_j^{\min} < x_i^{\min} < x_j^{\max} < x_i^{\max} \end{cases}$

손 할로는 교차하는 밧줄이 없도록 우주선을 다시 배치하려 한다. 게으른 성격이라 원래 위치 $x_i$에 그대로 남는 우주선의 수를 최대로 하고 싶다. 다시 배치한 뒤에도 우주선은 모두 정거장의 같은 쪽에 있어야 하고 위치가 서로 달라야 한다. 우주선은 임의의 실수 위치에 놓을 수 있다.

원래 위치에 남을 수 있는 우주선의 최대 개수를 구하라.

첫째 줄에 우주선의 수 $n$($1 \le n \le 200\,000$)이 주어진다. 둘째 줄에 우주선의 초기 위치를 나타내는 서로 다른 정수 $x_i$($1 \le x_i \le n$) $n$개가 주어진다.

원래 위치에 남을 수 있는 우주선의 최대 개수를 정수 하나로 출력한다.

첫 번째 예제에서 손 할로는 두 번째 우주선을 첫 번째 우주선과 세 번째 우주선 사이로 옮기면 되고, 나머지 세 대는 자리를 지킨다. 두 번째 예제에서는 교차하는 밧줄이 없으므로 네 대 모두 원래 자리에 남을 수 있다.