Gộp dãy toàn số 1

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số \(A\) chỉ gồm các số có giá trị 0 hoặc 1. Hãy đếm số lượt đổi chỗ ÍT NHẤT các phần tử để gộp được tất cả các số 1 trong dãy vào một miền liên tiếp?

Input

  • Dòng đầu tiên gồm số nguyên \(N\) chỉ số phần tử thuộc dãy (\(1 \leq N \leq 10^6\)).
  • Dòng thứ hai gồm \(N\) số nguyên thuộc mảng \(A\) (các phần tử cách nhau bởi dấu cách)

Output

  • Số lượt đổi chỗ ít nhất.

Example

Test 1

Input
5
1 0 1 0 1
Output
1

Test 2

Input
6
1 0 1 0 1 1
Output
1

Bình luận