Dãy số ~M~ phần tử ~B~ được gọi là dãy con của dãy số ~A~ gồm ~N~ phần tử nếu tồn tại một mã chuyển ~C~ gồm ~M~ phần tử thoả mãn ~B_i = A_{C_{i}}~ với mọi ~i = 1...M~ và ~1 \le C_1 < C_2 < ... < C_m \le N~.

Một cách chia dãy ~A~ thành các dãy con "được chấp nhận" nếu các dãy con này là các dãy không giảm và mỗi phần tử của dãy ~A~ thuộc đúng một dãy con.

Yêu cầu: Bạn hãy chia dãy con ban đầu thành ít dãy con nhất mà vẫn "được chấp nhận".

Input

Dòng đầu tiên ghi số ~N~ là số phần tử của dãy ~A~ (~N \le 10^{5}~).

~N~ dòng tiếp theo ghi ~N~ số tự nhiên là các phần tử của dãy ~A~ (~A_{i} \le 10^{9}~).

Output

Ghi một số duy nhất là số lượng dãy con ít nhất thỏa mãn.

Sample Input

4
1
5
4
6

Sample Output

2