Cho mảng số nguyên gồm n phần tử. Hãy tính tổng các phần tử chia hết cho 3 và nằm ở vị trí lẻ (tính từ 0).

Input

• Dòng đầu chứa số nguyên n (1 ≤ n ≤ 106)
• Dòng thứ hai chứa n số nguyên a₁, a₂, ..., aₙ (|aᵢ| ≤ 106)

Output

• Một số nguyên là tổng cần tìm

Ví dụ

Input:
6
5 9 3 6 8 12

Output:
27