Chia hết cho 3

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
nguyenthanhhoang
Dạng bài
Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên không âm \(a_1, a_2, ..., a_n\) đếm số dãy con liên tiếp từ \(l\) đến \(r\) (\(1\le l\le r\le n\)) thỏa mãn \(\sum_{l\le i < j \le r} a_i\times a_j\) chia hết cho 3.

Input

  • Dòng đầu tiên chứa số nguyên \(n\) (\(1\le n \le 5\cdot 10^5\)).
  • Dòng thứ hai chứa \(n\) số nguyên \(a_i\) (\(0\le a_i \le 10^9\)).

Output

  • Ghi ra số dãy con thỏa mãn.

Example

Test 1

Input 
3
5 23 2021
Output 
4

Test 2

Input 
5
0 0 1 3 3
Output 
15

Test 3

Input 
10
0 1 2 3 4 5 6 7 8 9
Output 
20

Bình luận