~mex(a)~ được định nghĩa là số nguyên không âm nhỏ nhất không xuất hiện trong mảng ~a~. Ví dụ, ~mex([1,0,2])=3~ và ~mex([1])=0~.

Cho mảng ~a~ gồm ~n~ số nguyên được đánh số từ ~1~ đến ~n~. Bạn có thể thực hiện thao tác sau đây tối đa một lần:

• Đầu tiên, chọn hai chỉ số ~l~ và ~r~ ~(1 \le l \le r \le n)~, gọi ~m=mex([a_l,a_{l+1},...,a_r])~.
• Sau đó, gán ~a_i=m~ với mọi ~l \le i \le r~.

Bạn hãy xác định giá trị lớn nhất của ~mex(a)~ sau khi thực hiện thao tác trên tối đa một lần.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^6)~.
• Dòng thứ hai chứa ~n~ số nguyên của mảng ~a~ ~(0 \le a_i \le n)~.

Output

• In ra giá trị lớn nhất của ~mex(a)~.

Examples

Sample Input 1

4
1 2 3 0

Sample Output 1

4

Sample Input 2

2
2 1

Sample Output 2

2

Scoring

• Subtask ~1~ ~-~ ~1000~ điểm: ~n \le 200~
• Subtask ~2~ ~-~ ~1000~ điểm: ~n \le 4000~
• Subtask ~3~ ~-~ ~1000~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ đầu tiên, ta không cần thực hiện thao tác và ~mex(a)=4~.

Trong ví dụ thứ hai, ta có thể chọn ~l=1~ và ~r=1~, khi đó ~mex([a_1])=0~. Mảng ~a~ trở thành ~[0,1]~ và ~mex(a)=2~.