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