Sắp xếp drone

Bài 4 bảng JUNIOR Vòng chung kết 2024.

Nam có ~n~ drone thuộc một trong hai loại: loại 1 và loại 2. Sau một buổi trình diễn, Nam tập hợp lại và xếp thành một dãy ~s_1, s_2, \ldots, s_n~, trong đó ~s_i=1~ hoặc ~s_i=2~ cho biết drone thứ ~i (1 \le i \le n)~ thuộc loại 1 hoặc loại 2. Nam muốn sắp xếp lại dãy drone để loại 1 xếp trước loại 2 chỉ bằng các thao tác đổi chổ hai drone cho nhau. Cụ thể, mỗi lượt Nam có thể tráo đổi drone ở vị trí ~i(1\le i \le n)~ với drone ở vị trí ~j(1 \le j \le n)~ cho nhau.

Hãy tính số lượt đổi chổ hai drone ít nhất cần thực hiện để tất cả các drone loại 1 xếp trước drone loại 2.

Input

Dòng đầu gồm số nguyên dương ~n~ thỏa ~n \le 10^5~.

Dòng thứ hai chứa ~n~ số nguyên ~s_1, s_2, \ldots, s_n~ thỏa ~1 \le s_i \le 2~.

Output

In ra một số nguyên là số lần đổi chổ hai drone ít nhất cần thực hiện.

Constraint

• Subtask 1 (20%): ~n = 2~.

• Subtask 2 (40%): ~n \le 5~.

• Subtask 3 (40%): Không có ràng buộc gì thêm.

Samples

2
1 2

0

5
2 2 1 1 2

2