시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB131746759.821%

문제

길이 $N$의 수열 $A$가 주어진다. 이 수열의 부분 수열 중에서 인접한 두 원소의 차이가 정확히 $1$이 되지 않도록 하는 가장 긴 부분 수열의 길이를 구하여라.

입력

첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 500\,000$)

둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le 10^9$)

출력

첫째 줄에 조건을 만족하는 부분 수열의 최대 길이를 출력한다.

예제 입력 1

2
1 2

예제 출력 1

1

예제 입력 2

5
1 2 2 1 1

예제 출력 2

3

예제 입력 3

7
10 13 11 12 10 13 11

예제 출력 3

5

노트

어떤 수열의 부분 수열(subsequence)이란, 원래 수열에서 몇 개의 원소를 제거하여 얻을 수 있는 수열을 의미한다. 예를 들어, 수열 $[1, 3, 5]$의 부분 수열로 가능한 것은 $[]$, $[1]$, $[3]$, $[5]$, $[1, 3]$, $[3, 5]$, $[1, 5]$, $[1, 3, 5]$가 있다.

W3sicHJvYmxlbV9pZCI6IjM1NDcyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjdkXHVhY2UwIFx1YWMwNFx1YjJlOFx1ZDU1YyBcdWJiMzhcdWM4MWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWUzOFx1Yzc3NCAkTiRcdWM3NTggXHVjMjE4XHVjNWY0ICRBJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWM3NTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVjNzc4XHVjODExXHVkNTVjIFx1YjQ1MCBcdWM2ZDBcdWMxOGNcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIFx1YzgxNVx1ZDY1NVx1ZDc4OCAkMSRcdWM3NzQgXHViNDE4XHVjOWMwIFx1YzU0YVx1YjNjNFx1Yjg1ZCBcdWQ1NThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJDEgXFxsZSBOIFxcbGUgNTAwXFwsMDAwJCk8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMCAkTiRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4ICRBXzEsIEFfMiwgXFxjZG90cywgQV9OJFx1Yzc3NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKCQxIFxcbGUgQV9pIFxcbGUgMTBeOSQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVjZDVjXHViMzAwIFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzViNFx1YjVhNCBcdWMyMThcdWM1ZjRcdWM3NTggXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNChzdWJzZXF1ZW5jZSlcdWM3NzRcdWI3ODAsIFx1YzZkMFx1Yjc5OCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTU4XHVjNWVjIFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzIxOFx1YzVmNCAkWzEsIDMsIDVdJFx1Yzc1OCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHViODVjIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjODNcdWM3NDAgJFtdJCwgJFsxXSQsICRbM10kLCAkWzVdJCwgJFsxLCAzXSQsICRbMywgNV0kLCAkWzEsIDVdJCwgJFsxLCAzLCA1XSRcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzU0NzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTaW1wbGUgYW5kIEVhc3kgUHJvYmxlbSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhIHNlcXVlbmNlICRBJCBvZiBsZW5ndGggJE4kLiBGaW5kIHRoZSBtYXhpbXVtIGxlbmd0aCBvZiBhIHN1YnNlcXVlbmNlIGluIHdoaWNoIHRoZSBkaWZmZXJlbmNlIGJldHdlZW4gYW55IHR3byBhZGphY2VudCBlbGVtZW50cyBpcyBub3QgZXhhY3RseSAkMSQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICROJC4gKCQxXFxsZSBOXFxsZSA1MDBcXCwgMDAwJCk8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zICROJCBpbnRlZ2VycyAkQV8xLEFfMixcXGNkb3RzICxBX04kLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiAoJDFcXGxlIEFfaVxcbGUgMTBeOSQpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG1heGltdW0gbGVuZ3RoIG9mIGEgc3Vic2VxdWVuY2Ugc2F0aXNmeWluZyB0aGUgY29uZGl0aW9uIG9uIHRoZSBmaXJzdCBsaW5lLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5BIHN1YnNlcXVlbmNlIG9mIGEgc2VxdWVuY2UgaXMgYSBzZXF1ZW5jZSB0aGF0IGNhbiBiZSBvYnRhaW5lZCBieSByZW1vdmluZyBzb21lIGVsZW1lbnRzIGZyb20gdGhlIG9yaWdpbmFsIHNlcXVlbmNlLiBGb3IgZXhhbXBsZSwgdGhlIHBvc3NpYmxlIHN1YnNlcXVlbmNlcyBvZiAkWzEsMyw1XSQgYXJlICRbXSQsICRbMV0kLCAkWzNdJCwgJFs1XSQsICRbMSwzXSQsICRbMyw1XSQsICRbMSw1XSQsIGFuZCAkWzEsMyw1XSQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d