Cho một hoán vị \(h_{1}, h_{2}, \ldots, h_{n}\) là một hoán vị của \(1, 2, \ldots, n\), bạn được thực hiện hai loại phép biến đổi sau:

• Chọn hai phần tử bất kì và tráo đổi, loại phép biến đổi này chỉ được thực hiện nhiều nhất một lần.
• Chọn hai phần tử kề nhau và tráo đổi, loại phép biến đổi này được thực hiện nhiều lần.

Yêu cầu: Tính số phép biến đổi ít nhất để đưa hoán vị \(h_{1}, h_{2}, \ldots, h_{n}\) thành hoán vị \(1, 2, \ldots, n\).

Input

• Dòng đầu chứa số nguyên \(n\) \((1 \leq n \leq 10^{5})\);
• Dòng thứ hai chứa \(n\) số nguyên \(h_{1}, h_{2}, \ldots, h_{n}\) là một hoán vị của \(1, 2, \ldots, n\).

Output

• In ra một số nguyên là số phép biến đổi ít nhất để đưa hoán vị \(h_{1}, h_{2}, \ldots, h_{n}\) thành hoán vị \(1, 2, \ldots, n\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n = 3\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 30\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 300\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 10000\).
• Subtask \(5\) (\(15\%\) số điểm): \(n \leq 10^{4}\).
• Subtask \(6\) (\(15\%\) số điểm): không có rằng buộc gì thêm.

Example

5
5 3 4 2 1

3