비밀의 방

그라비티 폴스 마을의 또 다른 비밀을 풀던 쌍둥이 디퍼와 메이블은 깊은 숲속으로 들어갔다가 버려진 집을 발견했다. 집은 매우 낡았고, 지하실에 숨겨진 방 하나를 빼면 눈에 띄는 것이 없었다. 방은 잠겨 있었고 문에는 인터폰이 달려 있었다.

디퍼는 무슨 일이 있어도 방을 열기로 했다. 이번에는 운이 좋았다. 일기장 한 페이지에서 인터폰에 입력해야 할 코드의 실마리를 찾았다. 일기에는 길이가 $n$인 수열 $a$가 적혀 있었고, 코드는 모든 두 원소의 쌍이 $a_i - a_j < j - i$를 만족하는 부분수열 중 원소 개수가 가장 많은 것이라고 했다. 디퍼가 코드의 길이를 구하도록 도와 달라.

첫 줄에 수열의 원소 개수 $n$이 주어진다 ($1 \le n \le 10^6$).

다음 줄에는 수열의 원소인 음이 아닌 정수 $a_i$가 주어진다 ($1 \le a_i \le 10^9$).

디퍼가 비밀의 방 문을 열 수 있는 코드에 들어가는 수의 개수를 한 줄에 출력한다.

첫 번째 테스트에서는 $a_0 = 1, a_1 = 2, a_2 = 2$이다. 모든 쌍을 확인하면 각 쌍에서 부등식이 성립함을 알 수 있다.

1. $a_0 - a_1 = 1 - 2 < 1 - 0$.
2. $a_1 - a_2 = 2 - 2 < 2 - 1$.
3. $a_0 - a_2 = 1 - 2 < 2 - 0$.

두 번째 테스트에서는 인덱스가 1, 2, 3, 4인 원소를 고르면 부등식이 성립한다. 원소를 더 많이 고르면 부등식이 성립하지 않는 쌍이 반드시 나타난다.