Adnan sở hữu cửa hàng giày lớn nhất ở Baku. Một hộp chứa \(n\) đôi giày vừa được chuyển đến cửa hàng. Mỗi đôi gồm hai chiếc giày có cùng kích cỡ: một chiếc bên trái và một chiếc bên phải. Adnan đã đặt tất cả \(2n\) chiếc giày thành một hàng gồm \(2n\) vị trí, được đánh số từ \(0\) đến \(2n-1\) theo thứ tự từ trái sang phải.

Adnan muốn sắp xếp lại các chiếc giày thành một sắp xếp hợp lệ. Một sắp xếp được gọi là hợp lệ khi và chỉ khi với mỗi \(i\) (\(0 \leq i \leq n-1\)), tất cả các điều kiện sau đều thỏa mãn:

• Các chiếc giày ở vị trí \(2i\) và \(2i+1\) có cùng kích cỡ.
• Chiếc giày ở vị trí \(2i\) là giày trái.
• Chiếc giày ở vị trí \(2i+1\) là giày phải.

Để đạt được mục tiêu này, Adnan có thể thực hiện một dãy các hoán đổi. Trong mỗi lần hoán đổi, anh ta chọn hai chiếc giày liền kề tại thời điểm đó và hoán đổi chúng (nghĩa là nhấc chúng lên và đặt từng chiếc giày vào vị trí cũ của chiếc giày kia). Hai chiếc giày liền kề nhau nếu vị trí của chúng khác nhau một đơn vị.

Hãy xác định số lần hoán đổi ít nhất mà Adnan cần thực hiện để có được một sắp xếp hợp lệ cho các chiếc giày.

Chi tiết cài đặt

Bạn cần cài đặt hàm count_swaps. Trong đề gốc, hàm được mô tả bằng chữ ký int64 count_swaps(int[] S). Với C++, khai báo chính xác trong tệp shoes.h là:

long long count_swaps(std::vector<int> S);

Tệp cài đặt C++ cần bao gồm header:

# include "shoes.h"

• \(S\): một mảng gồm \(2n\) số nguyên. Với mỗi \(i\) (\(0 \leq i \leq 2n-1\)), \(|S[i]|\) là một giá trị khác \(0\) bằng kích cỡ chiếc giày ban đầu được đặt ở vị trí \(i\). Ở đây, \(|x|\) là giá trị tuyệt đối của \(x\), bằng \(x\) nếu \(x>0\) và bằng \(-x\) nếu \(x<0\). Nếu \(S[i]<0\), chiếc giày ở vị trí \(i\) là giày trái; ngược lại, nó là giày phải.
• Hàm cần trả về số lần hoán đổi ít nhất giữa các chiếc giày liền kề để có được một sắp xếp hợp lệ. Giá trị trả về là số nguyên 64 bit.

Các ví dụ

Ví dụ 1

Xét lời gọi dưới đây:

count_swaps([2, 1, -1, -2])

Adnan có thể thu được một sắp xếp hợp lệ sau \(4\) lần hoán đổi.

Chẳng hạn, trước tiên anh ta có thể hoán đổi các chiếc giày \(1\) và \(-1\), tiếp theo \(1\) và \(-2\), sau đó \(-1\) và \(-2\), và cuối cùng là \(2\) và \(-2\). Anh ta sẽ có được sắp xếp hợp lệ \([-2, 2, -1, 1]\). Không thể có được bất kỳ sắp xếp hợp lệ nào với ít hơn \(4\) lần hoán đổi. Do đó, hàm cần trả về \(4\).

Ví dụ 2

Trong ví dụ dưới đây, tất cả các chiếc giày đều có cùng kích cỡ:

count_swaps([-2, 2, 2, -2, -2, 2])

Adnan có thể hoán đổi các chiếc giày ở vị trí \(2\) và \(3\) để thu được sắp xếp hợp lệ \([-2, 2, -2, 2, -2, 2]\), do đó hàm cần trả về \(1\).

Các ràng buộc

• \(1 \leq n \leq 100\,000\).
• Với mỗi \(i\) (\(0 \leq i \leq 2n-1\)), \(1 \leq |S[i]| \leq n\).
• Luôn có thể đạt được một sắp xếp hợp lệ các chiếc giày bằng cách thực hiện một dãy hoán đổi nào đó.
• Giới hạn thời gian: \(1\) 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 vào theo khuôn dạng sau:

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

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

Dữ liệu ví dụ 1

2
2 1 -1 -2

4

Dữ liệu ví dụ 2

3
-2 2 2 -2 -2 2

1

Nguồn: Đề thi chính thức IOI 2019, ngày thi 1, bài Shoes (Arranging Shoes); bản tiếng Việt, bản Markdown và gói đính kèm của ban tổ chức.