Bạn được cho một dãy số gồm n số nguyên a1 , a2, ..., an. Một thao tác được ghi nhận khi bạn thực hiện tăng hoặc giảm giá trị của bất kỳ số ai nào trong dãy lên 1 đơn vị (tức là ai = ai + 1 hoặc ai = ai - 1) và bạn có thể lặp đi lặp lại thao tác này vô số lần.

Thầy giáo muốn bạn hãy thực hiện các thao tác tăng giảm giá trị đó để thu được một dãy số mới sao cho tích của các phần tử trong dãy số mới này bằng 1.

Ví dụ: với n = 3 và dãy số gồm 3 phần tử là [1,-3,0] chúng ta có thể thực hiện tăng 2 lần số -3 (tức a2) đế trở thành - 1 và giảm 1 lần số 0 (tức a3) đế trở thành -1. Lúc này ta sẽ thu được dãy số mới là [1, -1, - 1] và tích các phần tử trong dãy số này bằng 1. Như vậy, bạn sẽ mất tông cộng 3 thao tác đề thực hiện ba lần tăng/giảm giá trị. Có nhiều cách khác nhau để thực hiện việc tăng giảm để dãy mới thu được có tích bằng 1, tuy nhiên sẽ không tồn tại cách nào ít hơn ba thao tác.

Yêu cầu: Cho dãy số a gồm n số nguyên, hãy tìm ra chi phí ít nhất để biến đổi dãy số a đã cho trở thành dãy mới với tích các phần tử trong dãy bằng 1.

Dữ liệu vào:

Dòng đầu là số nguyên dương n.

Dòng thứ 2 gồm n số nguyên a; (-10^9 ≤ ai ≤ 10^9) với mỗi số được cách nhau bởi một dấu cách.

Dữ liệu ra:

Chi phí ít nhất để biến đổi dãy số đã cho để trở thành dãy có tích các phần tử bằng 1.

Ràng buộc:

Có 50% số test của bài có 0 < n ≤ 100

Có 50% số test còn lại của bài có 0 < n ≤ 10^5

Ví dụ:

Input 01:

2
-1 1

Output 01:

2

Input 02:

5
-5 -3 5 3 0

Output 02:

13

Cho một xâu S có độ dài xâu không quá 10^4, chỉ gồm các kí tự tiếng Anh in hoa. Viết liên tiếp K lần xâu X được xâu S. Hỏi có bao nhiêu xâu TN được tạo ra bằng cách xoá các kí tự từ xâu S.

Đầu vào:

Dòng đầu tiên chứa xâu X

Dòng thứ hai chứa một số nguyên dương K (K <= 10^9)

Đầu ra: In ra kết quả của bài toán sau khi chia lấy dư cho 10^9 + 7

Input:

TNNT
2

Output:

8

Giải thích:

Xâu S có dạng TNNTTNNT. Các bộ vị trí tạo thành xâu TN thỏa mãn là (1,2), (1,3), (1,6), (1,7), (4,6), (4,7), (5,6), (5,7)

Một buổi tối nọ, HCN tổ chức một bữa tiệc ở quán cà phê của mình.

Có n người xuất hiện, người thứ i có chiều cao h;. Những bữa tiệc thì không thế thiếu đi những hoạt động vui vẻ nên HCN quyết định ghép các cặp hai người cho một trò chơi team-building của mình. Vì không muốn để cho các cặp đôi trông quá chênh lệch về chiều cao, HCN đã đưa ra yêu cầu:

Người thứ i và người thứ j (i ‡ j) có thể ghép cặp được với nhau nếu 90% * hj ≤ hi ≤ hj. Hai cách ghép cặp (i, j) và cặp (j, i) được coi là một.

Với số lượng người tham dự nhỏ HCN có thể dễ dàng tính ra được số cách ghép các cặp khác nhau, nhưng do đã lỡ tay mời quá nhiều người nên việc tính toán của HCN trở nên khó khăn hơn. Hãy giúp HCN làm công việc này nhé.

Đầu vào:

• Dòng đầu tiên chứa số nguyên dương n - Số người ở bữa tiệc (1 ≤ n ≤ 10^5).

• Dòng tiếp theo chứa n số nguyên dương h1, h2, h3, ..., hn tương ứng với chiều cao từng người (hi ≤ 10^9).

Đầu ra:

In ra số cách chọn các cặp khác nhau.

Input:

6
100 89 90 101 91 99

Output:

11

Cho một ma trận nhị phân A kích thước N x M chỉ chứa các số 0 và 1. Hãy tìm kích thước cạnh của hình vuông lớn nhất trong ma trận mà chỉ chứa toàn số 1.

Input:

• Dòng 1: Hai số nguyên N, M (1 ≤ N, M ≤ 2000).

• N dòng tiếp theo: Mỗi dòng chứa M số nguyên (chỉ 0 hoặc 1) biểu diễn ma trận A.

Output:

• Một số nguyên duy nhất là độ dài cạnh của hình vuông lớn nhất tìm được.

Vi dụ:

Input:

3 3
0 1 1
1 1 1
0 1 1

Output:

2

Giải thích: