考虑到区间 $gcd$ 等于区间 $min$ 的要求，我们假设 $a_i$ 是某些区间的最小值，那么我们通过二分可以找到一个最远的左端点 $L_i$，使得 $\text{gcd}(a_{L_i}, a_{L_i + 1}, \dots, a_i) = a_i$，且 $\min(a_{L_i}, a_{L_i + 1}, \dots, a_{i - 1}) > a_i$。
同理，我们可以找到一个最远的右端点 $R_i$，使得 $\text{gcd}(a_i, a_{i + 1}, \dots, a_{R_i}) == a_i$，且 $\min(a_{i + 1}, a_{i + 2}, \dots, a_{R_i}) > a_i$。
在二分的过程中，某个区间的 $gcd$ 可以先通过 $st$ 表预处理，再通过辗转相除法合并两个区间的 $gcd$，最小值最大值也可以通过 $st$ 表处理。
最终答案即为 $\sum_{i = 1}^n (R_i - i + 1) \times (i - L_i + 1)$，总时间复杂度 $O(n \log n \log V)$。

但是事实上我们没有必要做二分或求 $gcd$。
首先对于任意一个合法区间来说，若 $a_i$ 是区间 $[L, R]$ 内的最小值，那么有 $\text{gcd}(a_L, a_{L + 1}, \dots, a_R) = a_i$，也就是说，区间 $[L, R]$ 中的任意一个数都是 $a_i$ 的倍数。
假如我们求出了 $L_i$ 和 $R_i$，那么对 $a_i$ 来说，$a_{R_i + 1}$ 是右边第一个不是 $a_i$ 的倍数的元素，同理 $a_{L_i - 1}$ 是左边第一个不是 $a_i$ 的倍数或恰好和 $a_i$ 相等的元素。
可以发现，$L_i$ 和 $R_i$ 都可以通过一个类似于单调栈的栈结构去求解。

具体来说，对于 $R_i$，我们从左向右依次枚举 $a_i$，若 $a_i$ 不是栈顶元素的倍数，则将栈顶的右端点设为 $i - 1$，再将 $a_i$ 加入栈顶，即可求出所有的 $R_i$。对于 $L_i$ 同理。
这个过程和单调栈的过程相似，首先对于栈中的每一个元素，靠近栈顶的元素一定是靠近栈底的元素的倍数，相当于保证了越靠栈顶的元素对下一次进栈的元素要求越严格，和单调性类似。
如果在维护栈的过程中，有某个数的进栈会导致部分元素的弹出，那么一定是从栈顶开始依次连续弹出，如果栈中仍有元素剩余，说明进栈的元素一定是栈顶元素的倍数，也就保证了“单调性”。
利用这种栈结构，我们可以在 $O(n)$ 的时间内求出所有的 $L_i$、$R_i$，总时间复杂度 $O(n)$。
两种做法均可通过此题 。

O(n):

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }

    // 计算每个元素作为最小值时的右边界
    vector<int> r(n, -1);
    deque<int> q;
    for (int i = 0; i < n; ++i) {
        while (!q.empty() && (a[i] % a[q.back()] != 0 || a[i] == a[q.back()])) {
            r[q.back()] = i;
            q.pop_back();
        }
        q.push_back(i);
    }
    while (!q.empty()) {
        r[q.back()] = n;
        q.pop_back();
    }

    // 计算每个元素作为最小值时的左边界
    vector<int> l(n, -1);
    q.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!q.empty() && a[i] % a[q.back()] != 0) {
            l[q.back()] = i;
            q.pop_back();
        }
        q.push_back(i);
    }
    while (!q.empty()) {
        l[q.back()] = -1;
        q.pop_back();
    }

    // 计算满足条件的区间数量
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += (ll)(i - l[i]) * (r[i] - i);
    }

    cout << ans << endl;
    return 0;
}