D-蜃楼观光_牛客挑战赛56

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

传说中，三目是在蜃气楼作为猫侍应的妖怪，他总是在工作与摸鱼中切换，今天的三目准备在蜃气楼的商店街里摸鱼。

商店街上从左到右有 $n$ 个摊位，标号分别为 $1, 2, \ldots, n$ ，第 $i$ 个摊位有一个观光值 $w_i$ ，表示该摊位吸引人的程度。此外， $w_1, w_2, \ldots, w_n$ 恰好是一个 $1, 2, \ldots, n$ 的排列。三目的时间有限，因此他只能观光最多三个摊位。为此，三目定义完美观光路线 $(i, j, k)$ 为满足如下条件的三元组：

$1 \leq i < j < k \leq n$
$\gcd(w_i, w_j) \leq \gcd(w_j, w_k)$

其中， $\gcd(a, b)$ 表示 $a$ 与 $b$ 的最大公约数。

三目想知道一共有多少种完美观光路线。他正在匆忙赶去商店街的路上，因此请你帮他计算出这个结果。

输入描述:

第一行为一个整数  ()，表示商店街上摊位的个数。

第二行为  个用空格分隔的整数 ，表示每个摊位的观光值。

保证  是一个  的排列。

输出描述:

输出一行一个整数，表示一共有多少种完美观光路线。

示例1

输入

复制

5
1 2 3 4 5

输出

复制

说明

一共有  种完美观光路线：。

示例2

输入

复制

7
3 4 1 7 5 2 6

输出

复制