Sắp xếp hoán vị

Cho số nguyên dương $N$ và một hoán vị $p_1,p_2,\dots ,p_N$ của các số từ $1$ đến $N$. Mỗi thao tác, ta được chọn một dãy con liên tiếp từ vị trí $i$ đến vị trí $j$ ($1\le i\le j\le N$) 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$). Có thể thực hiện bao nhiêu thao tác tùy ý, các dãy con được chọn ở các thao tác khác nhau có thể giao nhau.

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

Dữ liệu vào

• 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 $p_1,p_2,\dots ,p_N$ là một hoán vị của các số từ $1$ đến $N$.

Dữ liệu ra

In ra chi phí nhỏ nhất để sắp xếp dãy hoán vị đã cho thành dãy tăng dần (in $0$ nếu dãy đã tăng dần).

Ràng buộc

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

Ví dụ