Cho dãy số gồm n số nguyên \(a_1, a_2, ..., a_n\).

Chia dãy thành 3 nhóm (các phần tử trong nhóm có thể không liên tiếp và mỗi nhóm có ít nhất một phần tử), gọi tổng các phần tử trong mỗi nhóm là trọng số của nhóm. Đếm số cách chia sao cho trọng số nhóm 1 và trọng số nhóm 2 nhỏ hơn trọng số nhóm còn lại.

Hai cách chia được xem là giống nhau: \((x, y, z)\); \((y, x, z)\) với \(x, y, z\) là trọng số của nhóm \(1\), nhóm \(2\) và nhóm \(3\)

Input Specification

• Dòng đầu tiên số nguyên dương \(n\) \((0< n \le 15)\).
• Dòng tiếp theo ghi n số nguyên dương \(a_i\) \((a_i \le 200)\).

Output Specification

• In ra kết quả bài toán

Sample Input

4
1 2 1 3

Sample Output

4

Giải thích: các cách chia thỏa mãn

{a1},{a2},{a3,a4}
{a3},{a2},{a1,a4}
{a1},{a3},{a2,a4}
{a1,a3},{a2},{a4}