发现每一个 \(f(l, r)\) 中的连通块总是一条链（一棵树）。
那么此时连通块的数量就等于点的数量减去边的数量。
先考虑点的总数，一个价值为 \(a_i\) 的点一定是在 \(l \leqslant a_i\) 且 \(r\geqslant a_i\) 的 \(f(l, r)\) 中才会有一个贡献，根据乘法原理，它会产生 \(a_i\times (n - a_i + 1)\) 的贡献。
再考虑边的总数，因为边是从 \(i\) 连向 \(i + 1\) 的，当且仅当 \(l\leqslant \min(a_i, a_{i + 1})\) 且 \(r\geqslant \max(a_i, a_{i + 1})\) 时，这条边才会有一个贡献，根据乘法原理，它会产生 \(\min(a_i, a_{i + 1})\times (n - \max(a_i,a_{i + 1}) + 1)\) 的贡献。
最后答案就显而易见了。
时间复杂度：\(\mathcal{O}(n)\)
代码：
const int N = 1e5 + 5;
int n, a[N];
int main() {
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
ll ans = 0;
for (int i = 1; i <= n; i++) ans += 1ll * a[i] * (n - a[i] + 1);
for (int i = 1; i < n; i++) ans -= 1ll * min(a[i], a[i + 1]) * (n - max(a[i], a[i + 1]) + 1);
cout << ans << endl;
return 0;
}