Đưa tích về một (Make Product Equal One)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho $n$ số nguyên $a_i$. Mỗi thao tác tốn $1$ và tăng hoặc giảm đúng một phần tử đi $1$. Hãy tìm chi phí nhỏ nhất để biến dãy sao cho tích của mọi phần tử bằng $1$.

Input

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số nguyên $a_i$.

Output

In chi phí nhỏ nhất.

Subtask

Các giới hạn chung:

• $1 \le n \le 10^5$.

• $-10^9 \le a_i \le 10^9$.

• Subtask 1 (20 điểm): $n \le 20$, $|a_i| \le 20$

• Subtask 2 (30 điểm): $n \le 5000$, $|a_i| \le 10^6$

• Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Input

5
-5 -3 5 3 0

Output

13

Giải thích

Đưa các số khác $0$ về dấu gần nhất: $-5\to-1$ tốn $4$, $-3\to-1$ tốn $2$, $5\to1$ tốn $4$, $3\to1$ tốn $2$; đưa $0$ về $1$ tốn $1$. Tổng $13$, và có hai số âm nên tích bằng $1$.