You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Tâm và Di đang yêu xa. Vào dịp sinh nhật Tâm, Di gửi tặng Tâm một hộp quà chứa nhiều món quà, trong đó có một hũ kẹo, bên ngoài ghi lời nhắn “Cho anh hũ kẹo em đang ăn nè”. Trong hũ kẹo chỉ còn đúng ba viên kẹo, gồm: một viên vị dưa hấu, một viên vị chanh muối và một viên vị nho. Ban đầu, Tâm dự định mỗi lần nhớ Di thì sẽ ăn một viên kẹo, nhưng nếu như vậy thì hũ kẹo sẽ hết trong chốc lát, bởi vì Tâm luôn nhớ Di. Vậy nên, Tâm đặt ra quy tắc như sau:

• Tâm sẽ ăn viên vị dưa hấu trước, sau đó mới ăn viên vị chanh muối, sau đó nữa mới ăn viên vị nho.

• Tâm liệt kê ra $n$ mốc thời gian, từ trước tới sau, được đánh số hiệu từ 1 tới $n$; mỗi viên kẹo sẽ được ăn trong một và chỉ một mốc thời gian trong số $n$ mốc này. Tâm gắn mỗi mốc thời gian với một số nguyên dương, mốc thời gian thứ i được gắn với số $a_i$ ($a_i\le{10}^9$); nếu $a_i$ chia hết cho 3, thì vào mốc thời gian thứ $i$ Tâm không thể ăn viên vị chanh muối hay viên vị nho; nếu $a_i$ chia 3 dư 1, thì vào mốc thời gian thứ $i$ Tâm không thể ăn viên vị dưa hấu hay viên vị nho; nếu $a_i$ chia 3 dư 2, thì vào mốc thời gian thứ $i$ Tâm không thể ăn viên vị dưa hấu hay viên vị chanh muối.

Chẳng hạn, với $n=8, a_1=7, a_2=6, a_3=2, a_4=10, a_5=3, a_6=4, a_7=9, a_8=8$, ⬤ là viên vị dưa hấu, ⬤ là viên vị chanh muối, ⬤ là viên vị nho, Tâm sẽ ăn ba viên kẹo được Di tặng như sau:

Yêu cầu

Cho $n$ số $a_1,a_2,\ldots,a_n$, hãy cho biết Tâm có bao nhiêu cách khác nhau để ăn hết ba viên kẹo theo quy tắc đã đặt ra. Hai cách được coi là khác nhau nếu có ít nhất một viên kẹo được ăn vào hai mốc khác nhau trong hai cách này.

Dữ liệu

Vào từ đầu vào chuẩn

• Dòng đầu tiên chứa số nguyên dương $n$.
• Dòng tiếp theo chứa $n$ số $a_1,a_2,\ldots,a_n$.

Kết quả

Ghi ra đầu ra chuẩn 1 số cách khác nhau để ăn hết ba viên kẹo theo quy tắc đã đặt ra.

Ví dụ

8
7 6 2 10 3 4 9 8

3

Giới hạn

Subtask 1 (30% số điểm): $n\le{10}^2$.

Subtask 2 (30% số điểm): $n\le{10}^4$.

Subtask 3 (40% số điểm): $n\le{10}^6$.