Dưới đây là một số phương pháp có thể sử dụng mà chúng ta có thể sắp xếp các phần tử của một mảng theo thứ tự tăng dần:

1. Ở mỗi bước, chọn hai phần tử liền kề và hoán đổi chúng.
2. Ở mỗi bước, chọn hai phần tử bất kỳ và hoán đổi chúng.
3. Tại mỗi bước, chọn bất kỳ phần tử nào và di chuyển nó đến vị trí khác.
4. Ở mỗi bước, chọn bất kỳ phần tử nào và di chuyển phần tử đó lên phía trước của mảng.

Cho một hoán vị của các số \(1,2,…,n\), hãy tính số bước tối thiểu để sắp xếp mảng bằng các phương pháp trên.

Input

• Dòng đầu tiên chứa một số nguyên \(n\)
• Dòng thứ hai chứa \(n\) số nguyên mô tả hoán vị

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)

Output

• In ra bốn số: số bước tối thiểu sử dụng mỗi phương pháp, mỗi số cách nhau bởi dấu cách

Example

8
7 8 2 6 5 1 3 4

20 6 5 6