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à ~[\sqrt{j - i + 1}]~ (lấy phần nguyên, ví dụ ~[\sqrt{10,3333}] = 10~).

Yêu cầu: Tính chi phí nhỏ nhất để sắp xếp dãy hoán vị đã cho thành dãy tăng dần.

Input

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

Output

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

Sample Input 1

5
3 1 4 2 5

Sample Output 1

2

Subtasks

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