Nguồn: Học sinh Giỏi THPT Hà Nội năm 2022 - 2023

Cho số nguyên dương \(N\) và dãy hoán vị từ \(1\) đến \(N\). Hãy tính tổng chi phí nhỏ nhất để sắp xếp dãy hoán vị ban đầu thành dãy tăng dần. Biết rằng có thể chọn một dãy con liên tiếp từ \(i\) đến \(j\) và sắp xếp lại dãy con này thành dãy tăng dần với chi phí là \(\lfloor \sqrt {j - i + 1} \rfloor\) (lấy phần nguyên, ví dụ \(\lfloor 10,3333 \rfloor = 10\)).

Input

Dữ liệu vào từ tệp văn bản SX.INP:

• Dòng đầu tiên chứa số nguyên dương \(N\) (\(1 \leq N \leq 10^6\));
• Dòng thứ hai chứa \(N\) số nguyên dương là hoán vị từ \(1\) đến \(N\).

Output

Kết quả ra tệp văn bản SX.OUT:

• Chi phí nhỏ nhất để sắp xếp dãy hoán vị đã cho thành dãy tăng dần.

Example

5
3 1 4 2 5

2

Note

• Chọn dãy con \([3, 1]\) mất chi phí \(1\) và chuyển dãy thành \([1, 3, 4, 2, 5]\), sau đó chọn dãy con \([3, 4, 2]\) với chi phí \(1\) để sắp xếp thành dãy \([1, 2, 3, 4, 5]\) với tổng chi phí là \(2\).

Constraint

• Có \(30\%\) số test ứng với \(30\%\) số điểm của bài thoả mãn \(N \leq 9;\)
• \(30\%\) số test tiếp theo ứng với \(30\%\) số điểm của bài thoả mãn \(N \leq 2000;\)
• \(30\%\) số test tiếp theo ứng với \(30\%\) số điểm của bài thoả mãn \(N \leq 10^5;\)
• \(10\%\) số test còn lại ứng với \(10\%\) số điểm của bài thoả mãn \(N \leq 10^6.\)