#include <iostream>
using namespace std;

const int MAXN = 10005;
int fa[MAXN]; // 父亲数组

// 查找 + 路径压缩
int find(int x) {
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]); // 路径压缩核心
}

// 合并
void merge(int a, int b) {
    int rootA = find(a);
    int rootB = find(b);
    if (rootA != rootB) {
        fa[rootA] = rootB; // 将a的根接到b的根上
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    // 初始化，每个元素自成一个集合
    for (int i = 1; i <= n; ++i) fa[i] = i;

    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            merge(x, y);
        } else if (op == 2) {
            if (find(x) == find(y)) {
                cout << "Y\n";
            } else {
                cout << "N\n";
            }
        }
    }
    return 0;
}

#include <iostream>
using namespace std;

const int MAXN = 1000005;
int heap[MAXN]; // 堆数组，下标从1开始
int heapSize = 0; // 当前堆的大小

// 向上调整
void shiftUp(int p) {
    while (p > 1) {
        if (heap[p] < heap[p / 2]) { // 小根堆，子比父小则交换
            swap(heap[p], heap[p / 2]);
            p /= 2;
        } else {
            break;
        }
    }
}

// 向下调整
void shiftDown(int p) {
    int child = p * 2; // 左孩子
    while (child <= heapSize) {
        // 选择左右孩子中较小的一个
        if (child + 1 <= heapSize && heap[child + 1] < heap[child]) {
            child++;
        }
        if (heap[child] < heap[p]) { // 孩子比父亲小则交换
            swap(heap[child], heap[p]);
            p = child;
            child = p * 2;
        } else {
            break;
        }
    }
}

// 插入
void push(int x) {
    heap[++heapSize] = x;
    shiftUp(heapSize);
}

// 弹出堆顶
void pop() {
    heap[1] = heap[heapSize--];
    shiftDown(1);
}

// 取堆顶
int top() {
    return heap[1];
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            push(x);
        } else if (op == 2) {
            cout << top() << endl;
        } else if (op == 3) {
            pop();
        }
    }
    return 0;
}

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

int main() {
    priority_queue<int, vector<int>, greater<int>> pq; // 小根堆
    int n;
    cin >> n;
    while (n--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x;
            cin >> x;
            pq.push(x);
        } else if (op == 2) {
            cout << pq.top() << endl;
        } else if (op == 3) {
            pq.pop();
        }
    }
    return 0;
}

#include <iostream>
using namespace std;

const int MAXN = 50005;
int fa[MAXN * 3]; // 三倍空间

int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int a, int b) {
    fa[find(a)] = find(b);
}

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= 3 * n; ++i) fa[i] = i; // 初始化

    int ans = 0;
    while (k--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (x > n || y > n) { // 条件2
            ans++;
            continue;
        }
        if (op == 1) { // x和y是同类
            // 如果x吃y，或者y吃x，则是假话
            if (find(x) == find(y + n) || find(y) == find(x + n)) {
                ans++;
            } else {
                merge(x, y);
                merge(x + n, y + n);
                merge(x + 2 * n, y + 2 * n);
            }
        } else { // op == 2, x吃y
            // 如果x和y是同类，或者y吃x，则是假话
            if (find(x) == find(y) || find(y) == find(x + n)) {
                ans++;
            } else {
                merge(x, y + n);       // x是y的天敌
                merge(x + n, y + 2 * n); // x的天敌是y的食物
                merge(x + 2 * n, y);     // x的食物是y
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq; // 小根堆
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        pq.push(a);
    }

    int total_cost = 0;
    // 当堆里不止一堆时，持续合并
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        int cost = a + b;
        total_cost += cost;
        pq.push(cost); // 将新的一堆放回
    }
    cout << total_cost << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;

queue<ll> q1, q2; // q1存px段，q2存x-px段
ll q0[100005]; // 原数组

int main() {
    int n, m, qq;
    double u, v, p;
    cin >> n >> m >> qq >> u >> v >> p;
    for (int i = 0; i < n; ++i) cin >> q0[i];
    sort(q0, q0 + n, greater<ll>()); // 降序排序

    ll delta = 0; // 全局增长量
    for (int i = 1; i <= m; ++i) {
        ll maxVal = -1e18;
        int src = -1; // 来源队列 0,1,2
        if (!q0.empty() && q0[0] > maxVal) maxVal = q0[0], src = 0;
        if (!q1.empty() && q1.front() > maxVal) maxVal = q1.front(), src = 1;
        if (!q2.empty() && q2.front() > maxVal) maxVal = q2.front(), src = 2;

        // 弹出最大值并加上全局增长量
        if (src == 0) pop_heap(q0, q0 + n), n--;
        else if (src == 1) q1.pop();
        else q2.pop();
        maxVal += delta;

        if (i % qq == 0) cout << maxVal << " ";

        // 切割
        ll l1 = floor(maxVal * u / v);
        ll l2 = maxVal - l1;
        delta += qq; // 其他蚯蚓长度增加
        // 新蚯蚓入队时要减去当前的全局增长量，保证相对性
        q1.push(l1 - delta);
        q2.push(l2 - delta);
    }
    cout << endl;
    // ... (输出最终所有蚯蚓长度，类似操作)
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
long long tree[MAXN];
int n, m;

int lowbit(int x) { return x & -x; }

void add(int x, int k) {
    while (x <= n) {
        tree[x] += k;
        x += lowbit(x);
    }
}

long long query(int x) {
    long long res = 0;
    while (x > 0) {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int a; cin >> a;
        add(i, a);
    }
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            add(x, y);
        } else {
            cout << query(y) - query(x - 1) << '\n';
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
long long tree[MAXN];
int n, m;

int lowbit(int x) { return x & -x; }

void add(int x, long long k) {
    while (x <= n) {
        tree[x] += k;
        x += lowbit(x);
    }
}

long long query(int x) {
    long long res = 0;
    while (x > 0) {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    long long last = 0, cur;
    for (int i = 1; i <= n; i++) {
        cin >> cur;
        add(i, cur - last); // 初始化差分数组
        last = cur;
    }
    while (m--) {
        int op, x, y;
        long long k;
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> k;
            add(x, k);
            add(y + 1, -k);
        } else {
            cin >> x;
            cout << query(x) << '\n';
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int LOG = 17; // 2^17 > 1e5
int st[MAXN][LOG + 1];
int lg[MAXN]; // 预处理 log2 值

void initLog(int n) {
    lg[1] = 0;
    for (int i = 2; i <= n; i++) {
        lg[i] = lg[i / 2] + 1;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    initLog(n);
    for (int i = 1; i <= n; i++) {
        cin >> st[i][0];
    }
    // 预处理 ST 表
    for (int j = 1; j <= LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
    // 查询
    while (m--) {
        int l, r;
        cin >> l >> r;
        int k = lg[r - l + 1];
        cout << max(st[l][k], st[r - (1 << k) + 1][k]) << '\n';
    }
    return 0;
}

bool check(long long mid) {
    fill(diff, diff + n + 1, 0);
    int cnt = 0;
    long long max_exceed = 0;
    for (int i = 0; i < m; i++) {
        if (dist[i] > mid) {
            cnt++;
            max_exceed = max(max_exceed, dist[i] - mid);
            int u = plan[i].u, v = plan[i].v, l = plan[i].lca;
            diff[u]++; diff[v]++; diff[l] -= 2; // 边差分
        }
    }
    if (cnt == 0) return true;
    // DFS 计算子树和，得到每条边实际被覆盖的次数
    dfs_sum(1, 0);
    for (int i = 2; i <= n; i++) { // 边 i 连接 i 和 father[i]
        if (edge_cover[i] == cnt && edge_weight[i] >= max_exceed) {
            return true;
        }
    }
    return false;
}

// 离散化并获取排名映射 pa, pb
// ... (排序、去重、二分查找等操作)

// 构造序列 c
for (int i = 1; i <= n; i++) {
    c[pa[i]] = pb[i]; // pa[i] 是 a[i] 的排名，pb[i] 是 b[i] 的排名
}
// 树状数组求序列 c 的逆序对
long long ans = 0;
for (int i = n; i >= 1; i--) {
    ans += query(c[i] - 1); // 查询比 c[i] 小的数有多少个（已插入的）
    add(c[i], 1);
}
cout << ans % MOD << endl;

// fa[u][k] 表示 u 的 2^k 级祖先
// minw[u][k] 表示 u 到 fa[u][k] 路径上的最小边权
void dfs(int u, int f, int w) {
    dep[u] = dep[f] + 1;
    fa[u][0] = f;
    minw[u][0] = w;
    for (int i = 1; i <= LOG; i++) {
        fa[u][i] = fa[fa[u][i-1]][i-1];
        minw[u][i] = min(minw[u][i-1], minw[fa[u][i-1]][i-1]);
    }
    for (auto &e : tree[u]) {
        if (e.v != f) dfs(e.v, u, e.w);
    }
}
int query(int x, int y) {
    if (find(x) != find(y)) return -1;
    if (dep[x] < dep[y]) swap(x, y);
    int res = INT_MAX;
    for (int i = LOG; i >= 0; i--) {
        if (dep[fa[x][i]] >= dep[y]) {
            res = min(res, minw[x][i]);
            x = fa[x][i];
        }
    }
    if (x == y) return res;
    for (int i = LOG; i >= 0; i--) {
        if (fa[x][i] != fa[y][i]) {
            res = min(res, min(minw[x][i], minw[y][i]));
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    res = min(res, min(minw[x][0], minw[y][0](@ref));
    return res;
}

#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;

ll a[MAXN];
struct Node {
    int l, r;
    ll sum, add; // sum为区间和，add为懒惰加法标记
} tree[MAXN << 2];

void pushup(int p) {
    tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}
void pushdown(int p) {
    if (tree[p].add) {
        int lc = p<<1, rc = p<<1|1;
        ll tag = tree[p].add;
        tree[lc].sum += tag * (tree[lc].r - tree[lc].l + 1);
        tree[rc].sum += tag * (tree[rc].r - tree[rc].l + 1);
        tree[lc].add += tag;
        tree[rc].add += tag;
        tree[p].add = 0;
    }
}
void build(int p, int l, int r) {
    tree[p].l = l; tree[p].r = r; tree[p].add = 0;
    if (l == r) {
        tree[p].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
    pushup(p);
}
void update(int p, int l, int r, ll val) {
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].sum += val * (tree[p].r - tree[p].l + 1);
        tree[p].add += val;
        return;
    }
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) update(p<<1, l, r, val);
    if (r > mid) update(p<<1|1, l, r, val);
    pushup(p);
}
ll query(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) return tree[p].sum;
    pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    ll res = 0;
    if (l <= mid) res += query(p<<1, l, r);
    if (r > mid) res += query(p<<1|1, l, r);
    return res;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n);
    while (m--) {
        int op, x, y;
        ll k;
        cin >> op >> x >> y;
        if (op == 1) {
            cin >> k;
            update(1, x, y, k);
        } else {
            cout << query(1, x, y) << endl;
        }
    }
    return 0;
}

struct Node {
    int l, r;
    ll sum, add, mul;
} tree[MAXN << 2];
void pushdown(int p) {
    int lc = p<<1, rc = p<<1|1;
    // 更新子节点的sum：先乘后加
    tree[lc].sum = (tree[lc].sum * tree[p].mul + tree[p].add * (tree[lc].r - tree[lc].l + 1)) % MOD;
    tree[rc].sum = (tree[rc].sum * tree[p].mul + tree[p].add * (tree[rc].r - tree[rc].l + 1)) % MOD;
    // 更新子节点的mul和add：注意add也要先乘
    tree[lc].mul = (tree[lc].mul * tree[p].mul) % MOD;
    tree[lc].add = (tree[lc].add * tree[p].mul + tree[p].add) % MOD;
    tree[rc].mul = (tree[rc].mul * tree[p].mul) % MOD;
    tree[rc].add = (tree[rc].add * tree[p].mul + tree[p].add) % MOD;
    // 清空父节点标记
    tree[p].mul = 1; tree[p].add = 0;
}
void update_add(int p, int l, int r, ll val) { /* 类似基础模板，但需考虑mul存在 */ }
void update_mul(int p, int l, int r, ll val) {
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].sum = (tree[p].sum * val) % MOD;
        tree[p].mul = (tree[p].mul * val) % MOD;
        tree[p].add = (tree[p].add * val) % MOD; // 关键！加法标记也要乘
        return;
    }
    pushdown(p);
    /* ... 递归更新左右子树 ... */
    pushup(p);
}

struct Node {
    int l, r;
    int sum;
    int l0, r0, m0, l1, r1, m1;
    int assign; // -1:无， 0:赋0， 1:赋1
    bool rev;
} tree[MAXN << 2];
void pushdown(int p) {
    int lc = p<<1, rc = p<<1|1;
    int lenL = tree[lc].r - tree[lc].l + 1;
    int lenR = tree[rc].r - tree[rc].l + 1;
    if (tree[p].assign != -1) {
        int v = tree[p].assign;
        // 对左儿子赋值
        tree[lc].sum = v * lenL;
        tree[lc].l0 = tree[lc].r0 = tree[lc].m0 = (v == 0 ? lenL : 0);
        tree[lc].l1 = tree[lc].r1 = tree[lc].m1 = (v == 1 ? lenL : 0);
        tree[lc].assign = v; tree[lc].rev = false; // 清空取反标记
        // 对右儿子赋值 (类似)
        tree[p].assign = -1;
    }
    if (tree[p].rev) {
        // 对左儿子取反：交换0和1的所有信息
        tree[lc].sum = lenL - tree[lc].sum;
        swap(tree[lc].l0, tree[lc].l1); swap(tree[lc].r0, tree[lc].r1); swap(tree[lc].m0, tree[lc].m1);
        tree[lc].rev ^= 1;
        // 对右儿子取反 (类似)
        tree[p].rev = false;
    }
}
// 区间取反操作
void update_rev(int p, int ql, int qr) {
    if (ql <= tree[p].l && tree[p].r <= qr) {
        int len = tree[p].r - tree[p].l + 1;
        tree[p].sum = len - tree[p].sum;
        swap(tree[p].l0, tree[p].l1); swap(tree[p].r0, tree[p].r1); swap(tree[p].m0, tree[p].m1);
        tree[p].rev ^= 1;
        return;
    }
    pushdown(p);
    /* ... 递归 ... */
    pushup(p); // pushup需要复杂合并左右儿子信息
}

void update_sqrt(int p, int l, int r) {
    if (tree[p].l == tree[p].r) { // 叶子节点，直接修改
        tree[p].sum = tree[p].mx = sqrt(tree[p].sum);
        return;
    }
    if (l <= tree[p].l && tree[p].r <= r && tree[p].mx <= 1) {
        return; // 整个区间都是0或1，无需修改
    }
    // 否则，需要递归修改
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) update_sqrt(p<<1, l, r);
    if (r > mid) update_sqrt(p<<1|1, l, r);
    pushup(p); // 更新sum和mx
}

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int heap[N], cnt = 0; // cnt 为当前堆的大小

void push(int x) {
    heap[++cnt] = x;
    int i = cnt;
    while (i > 1 && heap[i] < heap[i >> 1]) { // 上浮
        swap(heap[i], heap[i >> 1]);
        i >>= 1;
    }
}

void pop() {
    if (cnt == 0) return;
    heap[1] = heap[cnt--];
    int i = 1;
    while (i * 2 <= cnt) { // 下沉
        int child = i * 2;
        if (child + 1 <= cnt && heap[child + 1] < heap[child]) child++;
        if (heap[child] >= heap[i]) break;
        swap(heap[i], heap[child]);
        i = child;
    }
}

int top() {
    return heap[1];
}

int main() {
    int n, op, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d", &x);
            push(x);
        } else if (op == 2) {
            printf("%d\n", top());
        } else {
            pop();
        }
    }
    return 0;
}

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N]; // q为单调队列，存储下标

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    // 求最小值
    int hh = 0, tt = -1; // 队头，队尾
    for (int i = 1; i <= n; i++) {
        // 判断队头是否滑出窗口
        if (hh <= tt && q[hh] < i - k + 1) hh++;
        // 维护队列单调递增
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        q[++tt] = i;
        if (i >= k) printf("%d ", a[q[hh]]);
    }
    printf("\n");

    // 求最大值
    hh = 0, tt = -1;
    for (int i = 1; i <= n; i++) {
        if (hh <= tt && q[hh] < i - k + 1) hh++;
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        q[++tt] = i;
        if (i >= k) printf("%d ", a[q[hh]]);
    }
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;
const int N = 3e6 + 10;
int a[N], ans[N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    stack<int> stk; // 栈中存储下标
    for (int i = 1; i <= n; i++) {
        // 当前元素 a[i] 比栈顶对应的元素大，则找到了栈顶的答案
        while (!stk.empty() && a[i] > a[stk.top()]) {
            ans[stk.top()] = i;
            stk.pop();
        }
        stk.push(i);
    }
    // 栈中剩余的元素右侧没有更大的，答案为0
    while (!stk.empty()) {
        ans[stk.top()] = 0;
        stk.pop();
    }
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;
const int N = 1e7 + 10;
int a[N], ls[N], rs[N], fa[N]; // 左、右、父

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    stack<int> stk; // 单调递减栈，存储“右链”节点下标
    for (int i = 1; i <= n; i++) {
        int last = 0; // 记录上一个弹出的节点
        while (!stk.empty() && a[stk.top()] > a[i]) {
            last = stk.top();
            stk.pop();
        }
        // 弹出的最后一个节点成为当前节点的左孩子
        if (!stk.empty()) {
            rs[stk.top()] = i;
            fa[i] = stk.top();
        }
        if (last) {
            ls[i] = last;
            fa[last] = i;
        }
        stk.push(i);
    }
    // 输出
    for (int i = 1; i <= n; i++) {
        printf("%d %d %d\n", fa[i], ls[i], rs[i]);
    }
    return 0;
}

// dp[i] 表示跳到位置 i 的最大得分
dp[0] = a[0];
int hh = 0, tt = -1;
int ans = -INF;
// 注意起点是0，且可能跳不到终点N
for (int i = L; i <= N; i++) { // 从能第一次起跳的位置开始
    // 维护窗口 [i-R, i-L]
    while (hh <= tt && q[hh] < i - R) hh++; // 队头出窗
    int j = i - L; // 新进入窗口的候选位置
    if (j >= 0 && dp[j] != -INF) { // 如果位置j可达
        while (hh <= tt && dp[q[tt]] <= dp[j]) tt--;
        q[++tt] = j;
    }
    if (hh <= tt) {
        dp[i] = dp[q[hh]] + a[i];
        if (i + R > N) ans = max(ans, dp[i]); // 从i可以一步跳到终点外
    }
}
printf("%d\n", ans);

// 初始化 dp 为负无穷，dp[0] = 0
for (int i = 1; i <= T; i++) {
    // 1. 不交易的情况
    for (int j = 0; j <= MaxP; j++) dp[i][j] = max(dp[i][j], dp[i-1][j]);
    if (i <= W + 1) continue; // 无法进行上次交易
    int pre = i - W - 1;
    // 2. 买入
    int hh = 0, tt = -1;
    for (int j = 0; j <= MaxP; j++) {
        // 维护窗口 [j-AS[i], j-1]
        while (hh <= tt && q[hh] < j - AS[i]) hh++;
        // 将 k=j-1 加入队列
        int val = dp[pre][j-1] + AP[i] * (j-1);
        while (hh <= tt && dp[pre][q[tt]] + AP[i] * q[tt] <= val) tt--;
        q[++tt] = j-1;
        if (hh <= tt) {
            int k = q[hh];
            dp[i][j] = max(dp[i][j], dp[pre][k] - AP[i] * (j - k));
        }
    }
    // 3. 卖出 (类似，队列维护最大值)
    hh = 0, tt = -1;
    for (int j = MaxP; j >= 0; j--) {
        while (hh <= tt && q[hh] > j + BS[i]) hh++;
        int val = dp[pre][j+1] + BP[i] * (j+1);
        while (hh <= tt && dp[pre][q[tt]] + BP[i] * q[tt] <= val) tt--;
        q[++tt] = j+1;
        if (hh <= tt) {
            int k = q[hh];
            dp[i][j] = max(dp[i][j], dp[pre][k] + BP[i] * (k - j));
        }
    }
}
// 答案在 dp[T]

long long solve(int l, int r) {
    if (l > r) return 0;
    int mid = query(l, r); // 用ST表或笛卡尔树预处理区间最大值位置
    long long res = solve(l, mid-1) + solve(mid+1, r);
    // 统计跨mid的pair
    int maxv = a[mid];
    if (mid - l < r - mid) { // 枚举左半部分
        vector<int> right_vals;
        for (int j = mid; j <= r; j++) right_vals.push_back(a[j]);
        sort(right_vals.begin(), right_vals.end());
        for (int i = l; i <= mid; i++) {
            long long limit = maxv / a[i];
            // 在right_vals中找到 <= limit 的个数
            int cnt = upper_bound(right_vals.begin(), right_vals.end(), limit) - right_vals.begin();
            res += cnt;
        }
    } else { // 枚举右半部分，同理
        // ...
    }
    return res;
}