Hôm nay thầy Thành cho các bạn trong đội tuyển làm một bài kiểm tra về chủ đề phép chia hết. Thầy sẽ đưa cho mỗi bạn một số nguyên dương, và yêu cầu các bạn tính số lượng ước của số được đưa ra.

Do thầy Thành rất lười tạo ra các số nguyên dương khác nhau, thầy chỉ tạo ra một dãy số nguyên dương \(a\) gồm \(n\) phần tử \(a_1, a_2, a_3, \ldots, a_n\). Sau đó, với mỗi học sinh, thầy chọn ra một bộ ba chỉ số \((u, v, w)\) với \(1 \le u \le v < w \le n\), rồi tính các tổng \(s(u, v) = a_u + a_{u+1} + \ldots + a_v\), \(s(u, w) = a_u + a_{u+1} + \ldots + a_w\) và lấy kết quả \(x\) của phép tính \(x = s(u, w) - s(u, v)\) làm đề bài. Rất may, số học sinh của đội tuyển lại đúng bằng số lượng bộ chỉ số có thể chọn, nên thầy có thể chọn các bộ \((u, v, w)\) sao cho mỗi bạn đều có thể nhận được kết quả \(x\) từ các bộ chỉ số khác nhau (mặc dù có thể số nguyên dương mà các bạn nhận được là giống nhau).

Thầy Thành không muốn kiểm tra kết quả của từng bạn, nên thầy có một giải pháp đơn giản: cộng kết quả của tất cả các bạn lại rồi đối chiếu với đáp án, nếu tổng kết quả của các bạn là chính xác, tất cả các bạn trong đội tuyển sẽ được \(10\) điểm, ngược lại thì tất cả các bạn sẽ được \(0\) điểm. Tuy nhiên việc tính toán chính xác đáp án cũng mất rất nhiều thời gian và dễ sai sót, nên các bạn hãy tính toán giúp thầy Thành nhé.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) (\(1 \le n \le 5000\)).
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 5000\)).

Output

• Một dòng duy nhất gồm tổng cần tính.

Example

3
1 2 3

8

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 400\).
• Subtask \(4\) (\(20\%\) số điểm): \(a_i \le 500\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.