가장 긴 지그재그 부분수열

정수 수열이 지그재그이려면 인접한 두 원소의 관계가 엄격한 증가와 엄격한 감소를 번갈아 나타나야 한다. 맨 앞의 관계는 증가여도 되고 감소여도 된다. 원소가 하나뿐인 수열도 지그재그다.

정수 수열이 주어질 때, 지그재그인 가장 긴 부분수열의 길이를 구한다. 부분수열은 원래 순서를 지키면서 원소를 원하는 만큼 지워서 만든다.

예를 들어 수열 1 2 3 4 2에는 길이가 3인 지그재그 부분수열이 여럿 있다. 1 3 2, 1 4 2, 2 3 2, 2 4 2, 3 4 2가 모두 지그재그다. 길이가 4 이상인 것은 없으므로 답은 3이다.

첫째 줄에 수열의 길이 $n$이 주어진다 ($1 \le n \le 1000000$). 이어지는 $n$개의 줄에 수열의 원소 $k$가 한 줄에 하나씩 주어진다 ($1 \le k \le 1000000$).

가장 긴 지그재그 부분수열의 길이를 한 줄에 출력한다.