求公约数

题目描述

小翔有一个长度为 $n$ 的排列 $a$ 。定义一个区间 $[l，r]$ 的价值为：

$$\text{value}(l,r)=\max_{l\leq i<j\leq r}\left\{\gcd\left(a_{i}, a_{j}\right)\right\} $$

其中 $\gcd(i，j)$ 表示整数 $i$ ， $j$ 的最大公约数。

现在，小翔给了你一个任务：对于每个正整数 $x(1\leq x\leq n)$ ，你需要计算出有多少对 $l$ ， $r(1\leq l<r\leq n)$ ，满足 $\text{value}(l，r)=x$ 。

第一行一个正整数 $n$ ，表示排列的长度。

第二行 $n$ 个正整数 $a_{1}$ ， $a_{2}$ ， $\ldots$ ， $a_{n}$ ，来描述排列 $a$ 。

共 $n$ 行，第 $i$ 行输出当 $x=i$ 时的答案。

5
1 4 3 5 2

见gcd2.in

见gcd2.out

见gcd3.in

见gcd3.out