Mr. Chanek gives you a sequence a indexed from 1 to n. Define f(a) as the number of indices where a_i = i. 

You can pick an element from the current sequence and remove it, then concatenate the remaining elements together. For example, if you remove the 3-rd element from the sequence [4, 2, 3, 1], the resulting sequence will be [4, 2, 1]. 

You want to remove some elements from a in order to maximize f(a), using zero or more operations. Find the largest possible f(a).

Input

The first line contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the initial length of the sequence.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 2 ⋅ 10^5) — the initial sequence a.

Output

Output an integer denoting the largest f(a) that can be obtained by doing zero or more operations.

Examples

Input


7
2 1 4 2 5 3 7


Output


3


Input


4
4 2 3 1


Output


2

Note

In the first example, f(A) = 3 by doing the following operations.

[2,1,4,2,5,3,7] → [2,1,2,5,3,7] → [1,2,5,3,7] → [1,2,5,3] → [1,2,3]

In the second example, f(A) = 2 and no additional operation is needed.
import sys
sys.setrecursionlimit(100000)

def _r(): return sys.stdin.buffer.readline()
def rs(): return _r().decode('ascii').strip()
def rn(): return int(_r())
def rnt(): return map(int, _r().split())
def rnl(): return list(rnt())

# (2,-1) (1,1) (4,-1) (2,2) (5,0) (3,3) (7,0)
# 2 1 4 2 5 3 7
# 1 2 3 4 5 6 7

import bisect

def lis(a):
    dp = []
    for num in a:
        i = bisect.bisect_right(dp, num)
        if i == len(dp):
            dp.append(num)
        dp[i] = num
    return len(dp)

def solve(n, a):
    b = [(x, i+1-x) for i, x in enumerate(a)]
    b.sort(key=lambda x:(x[0], -x[1]))
    b = list(map(lambda x:x[1], b))
    return lis(b)

n = rn()
a = rnl()
print(solve(n, a))

# for _ in range(rn()):
#     n, x = rnt()
#     a = rnl()
#     print('YES' if solve(n, x, a) else 'NO')

# def solve(n, m, mat):
#     def _try(r, c, dr, dc):
#         sol = 0
#         for i in range(c+1, c+dc):
#             sol += 1 - int(mat[r][i])
#             sol += 1 - int(mat[r+dr][i])
#         for i in range(r+1, r+dr):
#             sol += 1 - int(mat[i][c])
#             sol += 1 - int(mat[i][c+dc])
#         for i in range(r+1, r+dr):
#             for j in range(c+1, c+dc):
#                 sol += int(mat[i][j])
#         return sol
#     sol = float('inf')
#     sols = [[0]*m for _ in range(n)]
#     for r in range(n-4):
#         for c in range(m-3):
#             dr = 4
#             while r+dr < n:
#                 dc = 3
#                 while c+dc < m:
#                     sols[r+dr][c+dc] = _try(r, c, dr, dc)
#                     sol = min(sol, _try(r, c, dr, dc))
#                     dc += 1
#                 dr += 1
#     for row in sols:
#         print(row)
#     return sol

# for _ in range(rn()):
#     n, m = rnt()
#     mat = []
#     for _ in range(n):
#         mat.append(rs())
#     print(solve(n, m, mat))