题目描述

给定一个由 $n$ 个整数构成的序列 $a_i$。

令 $\text{mul}(l, r) = \prod_{i = l}^{r} a_i$，并令 $\text{fac}(l, r)$ 表示 $\text{mul}(l, r)$ 的不同质因子的个数。

请计算 $\sum_{i = 1}^{n}\sum_{j = i}^{n}\text{fac}(i, j)$。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$) —— 序列的长度。

第二行包含 $n$ 个整数 $a_i$ ($1 \le i \le n, 1 \le a_i \le 10^6$) —— 该序列。

输出格式

输出该式的计算结果。

10
99 62 10 47 53 9 83 33 15 24

248

10
6 7 5 5 4 9 9 1 8 12

134

提示

翻译由 DeepSeek V4 Pro 完成