CaiWinDao rất thích có em gái. Có thể bạn chưa biết, CaiWinDao có 3 em gái và \(n\) gói kẹo, gói kẹo thứ \(i\) có \(a_i\) viên. Mỗi lần 3 em gái đến thăm, CaiWinDao sẽ chọn ra một vài gói kẹo sao cho tổng số kẹo trong các bao đó chia hết cho 3 rồi chia đều cho các em gái. CaiWinDao rất thích nói chuyện với các em gái nên muốn được các em thăm càng nhiều càng tốt. Các bạn hãy tính xem với \(n\) gói kẹo hiện tại, CaiWinDao sẽ rủ các em đến nhà được nhiều nhất bao nhiêu ngày?

Input

Dòng đầu gồm một số nguyên dương \(n (n \le 170901)\)

Dòng tiếp theo gồm \(n\) số nguyên dương \(a_i (a_i \le 170901)\) .

Output

Gồm một số nguyên là số ngày nhiều nhất CaiWinDao được gái thăm.

Example

4
1 6 2 1

2