Lập Phương Hoàn Hảo

Trong một buổi phỏng vấn thú vị, người dẫn chương trình đã đưa ra một thử thách hóc búa cho FullHouse Dev. Đội được yêu cầu phải tìm số lượng mảng con có tích các phần tử là số lập phương hoàn hảo. Với tinh thần nhiệt huyết, FullHouse Dev đã bắt tay vào giải quyết bài toán này.

Bài toán

Cho một mảng \(A\) gồm \(n\) số nguyên. Nhiệm vụ của FullHouse Dev là tìm số lượng mảng con mà tích các phần tử trong mảng con đó là một số lập phương hoàn hảo.

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên cách nhau bởi dấu cách, biểu diễn các phần tử của mảng.

OUTPUT FORMAT:

• In ra số lượng mảng con có tích các phần tử là số lập phương hoàn hảo.

Ràng buộc:

• \(1 \leq n \leq 10^5\)
• \(1 \leq A[i] \leq 10^9\)

Ví dụ

INPUT

4
2 4 6 36

OUTPUT

3

Giải thích

Ba mảng con có tích các phần tử là số lập phương hoàn hảo:

• Mảng con có tích là \(8\) (số lập phương của 2)
• Mảng con có tích là \(64\) (số lập phương của 4)
• Mảng con có tích là \(216\) (số lập phương của 6)