Thành phố Tehran là nơi đặt Thư viện Quốc gia Iran. Kho báu quý giá nhất của thư viện được trưng bày trong một căn phòng dài, trên một dãy gồm \(n\) chiếc bàn được đánh số từ \(0\) đến \(n-1\) theo thứ tự từ trái sang phải. Mỗi bàn đặt một quyển sách cổ viết tay. Các quyển sách đang được sắp xếp theo niên đại, khiến khách tham quan gặp khó khăn khi tìm sách theo tiêu đề. Vì vậy, người điều hành thư viện quyết định sắp xếp lại các quyển sách theo thứ tự từ điển của tiêu đề.

Aryan là nhân viên thư viện được giao công việc này. Anh đã lập một mảng \(p\) có độ dài \(n\), gồm các số nguyên phân biệt từ \(0\) đến \(n-1\). Mảng này mô tả vị trí đích của mỗi quyển sách: với mọi \(0 \le i < n\), quyển sách ban đầu ở bàn \(i\) phải được chuyển đến bàn \(p[i]\).

Aryan bắt đầu ở bàn \(s\) và phải quay lại bàn này sau khi sắp xếp xong. Vì sách rất quý giá, tại mỗi thời điểm anh chỉ được mang theo nhiều nhất một quyển. Anh có thể thực hiện một dãy thao tác, mỗi thao tác thuộc một trong các loại sau:

• Nếu không mang sách và bàn tại vị trí đang đứng có sách, anh có thể nhặt quyển sách đó lên.
• Nếu đang mang sách và bàn tại vị trí đang đứng có một quyển sách khác, anh có thể đổi quyển sách đang mang với quyển sách trên bàn.
• Nếu đang mang sách và bàn tại vị trí đang đứng không có sách, anh có thể đặt quyển sách đang mang xuống bàn đó.
• Anh có thể di chuyển đến bất kỳ bàn nào, khi không mang sách hoặc khi mang đúng một quyển sách.

Với mọi \(0 \le i,j \le n-1\), khoảng cách giữa bàn \(i\) và bàn \(j\), tính bằng mét, là:

Hãy tính tổng quãng đường nhỏ nhất Aryan cần di chuyển để đưa tất cả các quyển sách về đúng bàn đích và quay lại bàn \(s\).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau, được khai báo trong tệp books.h:

long long minimum_walk(std::vector<int> p, int s);

• p: mảng có độ dài \(n\). Với mọi \(0 \le i < n\), quyển sách ban đầu ở bàn \(i\) phải được chuyển đến bàn \(p[i]\).
• s: chỉ số bàn nơi Aryan bắt đầu và phải quay lại sau khi sắp xếp xong.
• Hàm phải trả về tổng quãng đường nhỏ nhất, tính bằng mét, để Aryan hoàn thành công việc và quay lại bàn xuất phát. Giá trị trả về có kiểu số nguyên 64 bit long long.

Ví dụ

Xét lời gọi:

minimum_walk({0, 2, 3, 1}, 0);

Trong ví dụ này, \(n=4\) và Aryan bắt đầu ở bàn \(0\). Anh có thể sắp xếp các quyển sách như sau:

1. Di chuyển đến bàn \(1\) và nhặt quyển sách ở đó lên. Quyển sách này cần được đặt ở bàn \(2\).
2. Di chuyển đến bàn \(2\) và đổi quyển sách đang mang với quyển sách trên bàn. Quyển sách vừa nhặt lên cần được đặt ở bàn \(3\).
3. Di chuyển đến bàn \(3\) và đổi quyển sách đang mang với quyển sách trên bàn. Quyển sách vừa nhặt lên cần được đặt ở bàn \(1\).
4. Di chuyển đến bàn \(1\) và đặt quyển sách đang mang xuống bàn này.
5. Quay lại bàn \(0\).

Quyển sách ban đầu ở bàn \(0\) đã nằm đúng vị trí nên Aryan không cần nhặt nó lên. Tổng quãng đường anh di chuyển là:

Đây là phương án tối ưu, nên hàm phải trả về \(6\).

Ràng buộc

• \(1 \le n \le 1\,000\,000\).
• \(0 \le s \le n-1\).
• Mảng \(p\) chứa \(n\) số nguyên phân biệt trong đoạn từ \(0\) đến \(n-1\), kể cả hai đầu mút.
• Giới hạn thời gian: \(2\) giây. Giới hạn bộ nhớ: \(1024\) MiB.

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\ s\).
• Dòng \(2\): \(p[0]\ p[1]\ \ldots\ p[n-1]\).

Trình chấm mẫu in một dòng chứa giá trị trả về của minimum_walk.

Dữ liệu mẫu

4 0
0 2 3 1

Kết quả mẫu

6