I am stuck on this problem.

Problem Synopsis:
You are given an array A of size N.
Consider an undirected edge-weighted graph with N nodes numbered from 1 to N such that for any two nodes i and j there is an undirected edge between i and j with weight |i-j| * max(A[i], A[j]).
Find the weight of the shortest path between two given nodes X and Y.

Input Format:
The first line contains a single integer T, the number of test cases.
The first line of each test case contains three integers N, X and Y.
The second line of each test case contains N integers, A[1] A[2] ... A[N].

Output Format
For each test case, print a single integer, the weight of the shortest path, on a separate line.

I have a working solution for the first 3 subtasks but have run out of ideas for the last one.
Any help would be appreciated.

#include <bits/stdc++.h>
using ll = long long;
using std::cin;
using std::cout;
using std::vector;
using std::min;
using std::max;
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--){
        ll n, dump;
        cin >> n >> dump >> dump;
        vector<ll> a(n);
        for (ll& x : a)
            cin >> x;
        vector<ll> ans(n), seq{0};
        for (ll idx = 1; idx < n; ++idx){
            ll safety = seq.front();
            while (!seq.empty() && a[seq.back()] > a[idx])
                seq.pop_back();
            ll prev_idx = seq.empty() ? safety : seq.back();
            ans[idx] = ans[prev_idx] + (idx - prev_idx) * max(a[prev_idx], a[idx]);
            seq.push_back(idx);
        }
        cout << ans.back() << '\n';
    }
}

I recently came across this blog post and decided to try some of its problems. I am stuck on this problem. I can think of a naive O(n^2) solution by iterating through all pairs but do not see any redundancy in this solution. I cannot see a way to make it sub-quadratic (other than using the fact that 1 ≤ ai ≤ 2.5 * 10^6, maybe?). Any hints would be appreciated.