Bạn được cho một mảng số nguyên ~N~ phần tử ~a1~, ~a2~, ..., ~aN~ Mỗi bước bạn có thể thực hiện một trong hai thao tác sau:

• Chọn một phần tử từ mảng và xóa nó khỏi mảng. Kết quả là độ dài của mảng giảm đi 1 ;
• Chọn một phần tử từ mảng và tăng giá trị của nó lên 1 đơn vị;

Không giới hạn số lần thực hiện. Nếu mảng hiện tại trở nên trống rỗng, thì không thể thực hiện thêm lần nào nữa.

Tính số lần thực hiện tối thiểu cần thiết để tổng các phần tử của mảng 𝑎 chia hết cho 3. Có thể bạn không cần di chuyển.

Lưu ý rằng tổng các phần tử của một mảng rỗng (mảng có độ dài 0) bằng 0 .

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên duy nhất N (1≤ N ≤ 100.000).
• Dòng thứ hai gồm N số a1, a2, ..., aN, mỗi số cách nhau một khoảng trắng (0 ≤ ai ≤ 1.000)
• Tổng của N phần tử không vượt quá 200.000

Dữ liệu ra

Số lần di chuyển tối thiểu.

Sample

Input

4
2 2 5 4

Output

1