31236번 - 볼록볼록

2차원 좌표평면상에 $N$개의 점 $ P_1, P_2, ... , P_N $이 주어진다. 다음 조건들을 만족하게 하는 두 정수 $l$과 $r$에 대하여, $r - l + 1$의 최댓값을 구해보자.

• $1\le l \lt r \le N$이고, $r - l + 1 \ge 3$이다.
• $P_l, P_{l + 1}, \cdots , P_r$가 반시계 방향 순서로 볼록 다각형을 이룬다. 이때, 모든 내각은 180도 미만이다.

첫째 줄에 점의 개수 $N$이 주어진다. $(3 \le N \le 300\,000)$

둘째 줄부터 $N$개의 줄에 걸쳐 두 정수 $x_i, y_i$가 주어진다. 각각 $i$번째 점의 $x$좌표와 $y$좌표를 의미한다. $(-10^9 \le x_i, y_i \le 10^9)$

입력으로 주어지는 모든 점은 서로 다르다.

문제의 조건들을 만족하게 하는 두 정수 $l$과 $r$에 대하여, $r - l + 1$의 최댓값을 출력하라. 만약 이러한 두 정수 $l$과 $r$이 없다면 $-1$을 출력하라.

볼록 다각형이란 경계의 두 점을 잇는 어떤 선분도 다각형 외부로 나가지 않는 단순 다각형(자기교차하지 않는 것)이다.