Cheow có ~N~ món quà, mỗi món có một trọng lượng nguyên dương. Cheow muốn chia toàn bộ ~N~ món quà này thành các dãy con tăng dần, sao cho:

• Mỗi món quà thuộc đúng một dãy.
• Trong mỗi dãy, trọng lượng các món quà luôn tăng dần theo thứ tự xuất hiện.

Cheow muốn biết ít nhất cần bao nhiêu dãy con tăng như vậy để chia hết toàn bộ quà.

Input

• Dòng đầu tiên là số nguyên ~N~ ~(1 ≤ N ≤ 3×10^4)~ — số lượng món quà.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~ ~(1 ≤ A_i ≤ 10^{6})~ — trọng lượng các món quà theo thứ tự ban đầu.

Output

• Một số nguyên duy nhất — số lượng dãy con tăng ít nhất cần chia.

📌 Example

Input

5
3 1 2 5 4

Output

2

💡 Explanation

Một cách chia hợp lệ:

• Dãy đầu tiên có độ dài lớn nhất là 3 là [1, 2, 4]
• Dãy tiếp theo có độ dài lớn nhất mà không tính các số của dãy trước là [3, 5]

->Tổng cộng 2 dãy.