You are given a sequence A of n integer numbers (1 ≤ A_i ≤ n). A subsequence of A has the form A_u, A_u+1 ... A_v (1 ≤ u ≤ v ≤ n). We are interested in subsequences that are permutations of 1, 2 ... k (k is the length of the subsequence).

Your task is to find the longest subsequence of this type.

Input

• Line 1: n (1 ≤ n ≤ 100000)
• Line 2: n numbers A₁, A₂ ... A_n (1 ≤ A_i ≤ n)

Output

A single integer that is the length of the longest permutation

Example

Input:
5
4 1 3 1 2

Output:
3