Gom các giá trị âm thành một khối

Bối cảnh

Trong một dây chuyền phân loại, các phần tử âm đại diện cho sản phẩm cần kiểm tra đặc biệt. Hệ thống có thể thực hiện thao tác duy nhất là đổi chỗ hai phần tử kề nhau. Mục tiêu là đưa tất cả phần tử âm về thành một khối liên tiếp, nhưng không yêu cầu khối phải nằm ở đầu hay cuối mảng. Thứ tự tương đối của các phần tử âm không cần thay đổi vì đổi chỗ kề nhau tối ưu có thể xem mỗi phần tử âm "di chuyển" tới một vị trí mục tiêu trong khối.

Bạn phải tìm số phép đổi chỗ kề nhau ít nhất. Nếu dãy có không quá một phần tử âm, đáp án là 0.

Bài Hard không còn là thao tác dịch mảng trực tiếp. Người làm phải chuyển trạng thái mảng sang dãy vị trí của các phần tử âm, rồi tối ưu vị trí bắt đầu của khối đích. Với n≤2000, có thể thử mọi vị trí khối và tính chi phí một cách minh bạch, không cần kỹ thuật nâng cao ngoài mảng và vòng lặp.

Một phép swap kề làm vị trí của một phần tử thay đổi đúng 1, nên tổng số bước cần thiết để đưa các vị trí âm pos[j] tới khối [start, start+m-1] là tổng khoảng cách tuyệt đối |pos[j]-(start+j)|.

Yêu cầu

1. Ghi lại vị trí các phần tử âm theo thứ tự tăng tự nhiên.
2. Thử mọi start sao cho khối m phần tử nằm trong mảng.
3. Tính tổng khoảng cách từ pos[j] tới start+j; lấy min.

Input

Dòng 1: n. Dòng 2: n số nguyên.

Output

Một số nguyên: số phép đổi chỗ hai phần tử kề nhau ít nhất.

Ràng buộc

1 ≤ n ≤ 2000, |a[i]| ≤ 10^9.

Ví dụ 1

Input

7
1 -2 3 -4 -5 6 7

Output

1

Giải thích

Các phần tử âm nằm tại các index 1,3,4, vì vậy cần gom ba vị trí này thành một block ba ô liên tiếp mà vẫn giữ thứ tự tương đối của các số âm. Nếu chọn block đích 2,3,4, tổng số bước dịch kề nhau là |1-2| + |3-3| + |4-4| = 1. Các block khác tốn ít nhất 2 bước, ví dụ đích 1,2,3 có cost 0+1+1=2. Do đó số swap kề nhau tối thiểu là 1.

Ví dụ 2

Input

5
1 2 3 4 5

Output

0

Giải thích

Dãy 1 2 3 4 5 không có phần tử âm, nên không có đối tượng nào cần di chuyển hay gom nhóm. Theo xử lý biên, khi số phần tử âm m ≤ 1 thì chi phí tối thiểu bằng 0. Vì vậy output là 0.

Thông tin học tập

• Module: M03
• Buổi: B10
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: static arrays, positions, adjacent swaps, optimization, contiguous block, brute force
• Giới hạn kiến thức: B01-B10
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100