Cho một dãy số nguyên dương \(a_1, a_2, \ldots, a_n\). Đếm số cặp \((l, r)\) sao cho \(1 \le l \le r \le n\) và \(a_l \times a_{l + 1} \times \ldots \times a_r\) là số chính phương.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) (\(1 \le n \le 5 \cdot 10^5\)).
• 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 5 \cdot 10^6\)).

Output

• Một dòng duy nhất gồm số cặp \((l, r)\) tìm được.

Example

5
1 2 8 4 4

10

Scoring

• \(10\%\) số điểm có \(1 \le n \le 10\) và \(1 \le a_i \le 12\).
• \(12\%\) số điểm tiếp theo có \(1 \le n \le 100\), trong đó:
  • \(6\%\) số điểm có \(1 \le a_i \le 100\).
  • \(6\%\) số điểm còn lại có \(1 \le a_i \le 10^5\).
• \(30\%\) số điểm tiếp theo có \(1 \le n \le 1000\), trong đó:
  • \(8\%\) số điểm có \(a_i\) là số nguyên tố.
  • \(8\%\) số điểm khác có \(1 \le a_i \le 100\).
  • \(8\%\) số điểm khác có \(1 \le a_i \le 1000\).
  • \(6\%\) số điểm còn lại có \(1 \le a_i \le 5 \cdot 10^6\).
• \(48\%\) số điểm còn lại có \(1 \le n \le 5 \cdot 10^5\), trong đó:
  • \(10\%\) số điểm có \(a_i = 1\).
  • \(10\%\) số điểm khác có \(a_i = 2\).
  • \(8\%\) số điểm khác có \(1 \le a_i \le 2\).
  • \(8\%\) số điểm khác có \(1 \le a_i \le 3\).
  • \(6\%\) số điểm khác có \(1 \le a_i \le 100\).
  • \(4\%\) số điểm khác có \(1 \le a_i \le 10^5\).
  • \(2\%\) số điểm còn lại có \(1 \le a_i \le 5 \cdot 10^6\).