For each position, think: how many times do I divide this number by 2 until it becomes the parity I need (even/odd)? If it never reaches that parity, this pattern is impossible.

We observe that there are only two possible valid arrangements of parities in the final array:
even, odd, even, odd, ...
odd, even, odd, even, ...

So we simply try both patterns.For a fixed pattern, consider one element x.We are allowed to repeatedly replace it with x,⌊x/2⌋, ⌊x/4⌋,... Until the number becomes 0. This means after about $$$log(x)$$$ operations the value will never change again.Instead of actually dividing, we use bit shifts.

For each position we find the smallest k such that (x>>k) has the required parity. If such a k does not exist, then the current pattern is impossible.We compute the total cost (sum of all chosen k) for:
even, odd, even, odd, ...
odd, even, odd, even, ...

The answer is the minimum of the two results; if both are impossible, we output −1.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll llmax=LLONG_MAX;

ll func(int x,int d){
    for(int k=0;k<=32;k++){
        int v=x>>k;
        if((v&1)==d) return k;
    }
    return llmax;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    ll ans=llmax;
    // pattern: even,odd,even,odd...
    ll cur=0;
    for(int i=0;i<n;i++){
        int d=(i%2==0?0:1);
        ll c=func(a[i],d);
        if(c==llmax){
            cur=llmax;
            break;
        }
        cur+=c;
    }
    ans=min(ans,cur);
    // pattern: odd,even,odd,even...
    cur=0;
    for(int i=0;i<n;i++){
        int d=(i%2==0?1:0);
        ll c=func(a[i],d);
        if(c==llmax){
            cur=llmax;
            break;
        }
        cur+=c;
    }
    ans=min(ans,cur);

    if(ans==llmax) ans=-1;
    cout<<ans<<"\n";
}

n <= 1000, so we can precompute all the meeting times. It will take O($$${n^2}$$$) time only.

Pick every pair of cars, and store the time at which they meet.

Sort the meeting times. Now, for each query, you can do binary search on the sorted vector to find the earliest meeting >= startTime and latest meeting <= endTime.

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
#define pb push_back

const ll INF = 1e18;

vector<ll> solve()
{
    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    for (ll &x : a)
        cin >> x;
    vector<int> b(n);
    for (int &x : b)
        cin >> x;
    vector<ll> c;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
        {
            if (b[i] != b[j])
            {
                if (a[i] < a[j])
                {
                    if (b[i] == 1 && b[j] == -1)
                        c.pb(a[j] - a[i]);
                }
                else
                {
                    if (b[i] == -1 && b[j] == 1)
                        c.pb(a[i] - a[j]);
                }
            }
        }
    sort(c.begin(), c.end());
    int sz = c.size();
    vector<ll> ansa(q);
    for (int i = 0; i < q; i++)
    {
        ll s, e;
        cin >> s >> e;
        s *= 2;
        e *= 2;
        int ma1 = -1, ma2 = -1;
        {
            int l = 0, h = sz - 1;
            while (l <= h)
            {
                int m = (l + h) / 2;
                if (c[m] < s)
                    l = m + 1;
                else
                {
                    ma1 = m;
                    h = m - 1;
                }
            }
        }
        if (ma1 != -1)
        {
            {
                int l = 0, h = sz - 1;
                while (l <= h)
                {
                    int m = (l + h) / 2;
                    if (c[m] > e)
                        h = m - 1;
                    else
                    {
                        ma2 = m;
                        l = m + 1;
                    }
                }
            }
        }
        if(ma1 != -1) ansa[i] = ma2 - ma1 + 1;
        else ansa[i] = 0;
    }
    return ansa;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t--)
    {
        vector<ll> ansa = solve();
        for(ll x: ansa) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

You will always make the prices of the k items equal to the GCD of their prices.

GCD is an associative function. You can use 2 stacks to compute GCD of sliding window of size k.

Let us calculate the minimum number of operations now. Define $$$ca(x)$$$ as the number of times, we have to divide x by a prime number to make it 1.

Let, in current window, elements are $$${x_1}$$$, $$${x_2}$$$, $$${x_3}$$$, ..., $$${x_k}$$$. Let GCD of these k elements = $$$g$$$. Then, cost for this window = $$$(ca[x_1] + ca[x_2] + \cdots + ca[x_k]) — k * ca[g].$$$

Answer will be the minimum cost over all the sliding windows of size k.

Precompute $$$ca(x)$$$ for all the values.

#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;
#define pb push_back

const int INF = 1e8;
const int maxp = 1002;

int gct[maxp + 1][maxp + 1];

ll solve()
{
    for(int i = 0; i <= maxp; i++) gct[0][i] = i;
    for(int i = 1; i <= maxp; i++) gct[i][0] = i;
    for(int i = 1; i <= maxp; i++) for(int j = 1; j <= maxp; j++){
        if(i <= j) gct[i][j] = gct[j % i][i];
        else gct[i][j] = gct[i % j][j];
    }
    vector<int> spa(maxp + 1, 0);
    spa[1] = 1;
    vector<int> pms;
    for(int i = 2; i <= maxp; i++){
        if(spa[i] == 0){
            spa[i] = i;
            pms.pb(i);
        }
        for(int p: pms){
            if(i * p <= maxp) spa[i * p] = p;
            else break;
            if(i % p == 0) break;
        }
    }
    vector<int> ca(maxp + 1);
    for(int i = 1; i <= maxp; i++){
        int cnt = 0;
        int x = i;
        while(x > 1){
            x = x / spa[x];
            cnt++;
        }
        ca[i] = cnt;
    }
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int& x: a) cin >> x;
    vector<int> v1, v2;
    v1.reserve(n);
    v2.reserve(n);
    int ans = INF;
    int sm = 0;
    {
        int gc = 0;
        for(int i = 0; i < k; i++) {
            sm += ca[a[i]];
            gc = gct[gc][a[i]];
            v2.pb(gc);
        }
    }
    ans = min(ans, sm - k * ca[v2.back()]);
    for(int i = k; i < n; i++){
        if(v1.empty()){
            int gc = 0;
            for(int j = i - 1; j + k >= i; j--){
                v2.pop_back();
                gc = gct[gc][a[j]];
                v1.pb(gc);
            }
        }
        v1.pop_back();
        {
            int gc = v2.size() ? v2.back() : 0;
            v2.pb(gct[gc][a[i]]);
        }
        sm -= ca[a[i - k]];
        sm += ca[a[i]];
        int mgc = gct[v1.size() ? v1.back() : 0][v2.size() ? v2.back() : 0];
        ans = min(ans, sm - k * ca[mgc]);
    }
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--)
    {
        ll x = solve();
        cout << x << "\n";
    }
    return 0;
}

Any valid path containing the special point can be split into a part before it and a part after it.

After filtering points on each side, the problem becomes finding a longest increasing subsequence.

Solution Approach (Split + LIS)

1. Read all points and store the special point $$$P_k$$$.

2. Split the points into two sets:

• Left set: all points such that $$$x$$$ < $$$x_k$$$ and $$$y$$$ < $$$y_k$$$.
• Right set: all points such that $$$x$$$ > $$$x_k$$$ and $$$y$$$ > $$$y_k$$$.

1. Sort both sets by:

• $$$x$$$ in increasing order
• if $$$x$$$ is equal, $$$y$$$ in decreasing order

1. Compute:

• $$$L$$$ = length of the Longest Increasing Subsequence (LIS) of the y values in the left set
• $$$R$$$ = length of the Longest Increasing Subsequence (LIS) of the y values in the right set

1. The final answer is: $$$L + 1 + R$$$

The +1 accounts for the special point $$$P_k$$$ itself.

#include <bits/stdc++.h>
using namespace std;

struct pt {
    long long x, y;
};

int solve(vector<pt>& pts) {
    vector<long long> lis;
    for (auto& p : pts) {
        auto it = lower_bound(lis.begin(), lis.end(), p.y);
        if (it == lis.end())
            lis.push_back(p.y);
        else
            *it = p.y;
    }
    return lis.size();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n>> k;

    vector<pt> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >>a[i].y;
    }

    pt pk = a[k];

    vector<pt> left,right;

    for (int i = 0;i < n; i++) {
        if (a[i].x < pk.x && a[i].y < pk.y)
            left.push_back(a[i]);
        else if (a[i].x > pk.x && a[i].y > pk.y)
            right.push_back(a[i]);
    }

    auto cmp = [](const pt& p1, const pt& p2) {
        if (p1.x != p2.x) return p1.x < p2.x;
        return p1.y > p2.y;
    };

    sort(left.begin(), left.end(), cmp);
    sort(right.begin(),right.end(), cmp);

    int leftLIS = solve(left);
    int rightLIS = solve(right);

    cout << leftLIS + 1 +rightLIS << "\n";

    return 0;
}

Handling deletions online is hard.
But if we process time backwards, every deletion becomes an edge insertion, which DSU can handle easily.

Values only decrease forward in time.
So going backward, each value only increases — and we just need to maintain the maximum value per component.

The challenge is that bridges are deleted over time, and DSU cannot split components. Processing events forward would require handling edge deletions, which is complicated. Instead, we solve the problem by processing everything backwards. We first read all operations and simulate their effects only to learn the final state: which edges survive and what each city’s final value is after all decreases. Using this final state, we build a DSU, where each node starts with its final value, and we unite only edges that were never deleted.

Then we traverse the operations in reverse.
When we see a query, we simply return the maximum value stored in the component of that node.
When we reverse a deletion, the bridge effectively reappears, so we union its endpoints.
When we reverse a value decrease, the city’s value increases back to the previous one, so we update the component maximum. Since in reverse time we only add edges and increase values, DSU with a component maximum is enough.

#include <bits/stdc++.h>
using namespace std;

struct Op {
    char type;
    int a;
    int b;
    int old;
    int idx;
    int time;
};

int findp(vector<int>& parent, int x) {
    return parent[x] == x ? x : parent[x] = findp(parent, parent[x]);
}

void unite(int x, int y, vector<int>& parent, vector<int>& sz, vector<int>& comp_max) {
    x = findp(parent, x);
    y = findp(parent, y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    parent[y] = x;
    sz[x] += sz[y];
    comp_max[x] = max(comp_max[x], comp_max[y]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> initVal(n);
    for (int i = 0; i < n; ++i) cin >> initVal[i];

    vector<pair<int,int>> edges(m);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v; --u; --v;
        edges[i] = {u, v};
    }

    int q; cin >> q;
    vector<Op> ops; ops.reserve(q);
    vector<int> curVal = initVal;
    vector<char> edgeEverDeleted(m, 0);

    for (int i = 0; i < q; ++i) {
        char tp; cin >> tp;
        if (tp == 'D') {
            int e, t; cin >> e >> t; --e;
            Op op; op.type='D'; op.a=e; op.idx=i; op.time=t;
            ops.push_back(op);
            edgeEverDeleted[e] = 1;
        } else if (tp == 'U') {
            int v, x, t; cin >> v >> x >> t; --v;
            Op op; op.type='U'; op.a=v; op.b=x; op.idx=i; op.time=t;
            op.old = curVal[v];
            curVal[v] = x;
            ops.push_back(op);
        } else if (tp == 'Q') {
            int u, t; cin >> u >> t; --u;
            Op op; op.type='Q'; op.a=u; op.idx=i; op.time=t;
            ops.push_back(op);
        }
    }

    vector<int> finalVal = curVal;
    vector<int> parent(n), sz(n,1), comp_max(n);
    iota(parent.begin(), parent.end(), 0);
    for (int i = 0; i < n; ++i) comp_max[i] = finalVal[i];

    for (int eid = 0; eid < m; ++eid) {
        if (!edgeEverDeleted[eid]) {
            unite(edges[eid].first, edges[eid].second, parent, sz, comp_max);
        }
    }

    vector<int> ansByIdx(q, INT_MIN);

    for (int i = q - 1; i >= 0; --i) {
        const Op &op = ops[i];
        if (op.type == 'Q') {
            int u = op.a;
            int root = findp(parent, u);
            ansByIdx[op.idx] = comp_max[root];
        } else if (op.type == 'D') {
            int eid = op.a;
            unite(edges[eid].first, edges[eid].second, parent, sz, comp_max);
        } else if (op.type == 'U') {
            int v = op.a;
            int oldVal = op.old;
            int root = findp(parent, v);
            comp_max[root] = max(comp_max[root], oldVal);
        }
    }

    for (int i = 0; i < q; ++i) {
        if (ansByIdx[i] != INT_MIN) cout << ansByIdx[i] << '\n';
    }

    return 0;
}

Try to express the beauty of the array in terms of how the array is divided into contiguous segments.

Fix a segment $$$[l,r]$$$. Suppose you want all elements in this segment to become equal. How would you compute the minimum number of operations required?

if $$$k \ge 3n$$$, ans = $$$n - 1$$$

We are given an array $$$a_1,a_2,\dots,a_n$$$.
The beauty of the array is the number of indices $$$i$$$ such that $$$a_i = a_{i+1}$$$.

If $$$k \ge 3n$$$, all elements can be made equal, by making each element of an array equal to 1 because converting any number to 1 takes atmost $$$3$$$ operations,yielding beauty $$$n-1$$$.So for rest of solution we assume $$$k \lt 3n$$$

Observe that if the final array consists of $$$S$$$ contiguous segments of equal values, then the beauty is $$$n-S$$$.
Hence, the problem reduces to minimizing the number of constant segments after at most $$$k$$$ operations.

All allowed operations strictly decrease a value, so an element $$$x$$$ can only be transformed into values in the range $$$[1,x]$$$.
We first precompute the minimum number of operations required to convert any value $$$x$$$ into any smaller value $$$v$$$.
Let $$$\text{cost}(v,x)$$$ denote this minimum.
It is computed using dynamic programming over values, considering both decrement operations and division by proper divisors.

For a segment $$$[l,r]$$$, if we want to make all its elements equal to some value $$$v$$$, the total cost is $$$\sum_{i=l}^{r} \text{cost}(v, a_i)$$$

where $$$v \le \min(a_l,a_{l+1},\dots,a_r)$$$. Using prefix sums of $$$\text{cost}(v,\cdot)$$$, this segment cost can be computed efficiently.
The minimum cost to make the segment $$$[l,r]$$$ constant is obtained by trying all valid values of $$$v$$$.

We now define a dynamic programming solution.
Let $$$f[i][j]$$$ be the minimum number of constant segments needed to cover the prefix $$$[1,i]$$$ using exactly $$$j$$$ operations.
The base case is $$$f[0][0] = 0.$$$

To compute $$$f[i][j]$$$, we end the last segment at position $$$i$$$ and let it start at position $$$l$$$ with $$$1 \le l \le i$$$.
If the cost to make the segment $$$[l,i]$$$ constant is $$$\text{segCost}(l,i)$$$, then for all $$$j \ge \text{segCost}(l,i)$$$,

$$$f[i][j] = \min\big(f[i][j],\, f[l-1][j-\text{segCost}(l,i)] + 1\big).$$$

While extending the segment leftwards, the minimum value in $$$[l,i]$$$ only decreases, so the number of valid target values remains small.

Finally, the minimum number of segments is $$$\min_{0 \le j \le k} f[n][j],$$$ and the maximum achievable beauty is $$$n — \min_{0 \le j \le k} f[n][j].$$$

The preprocessing of $$$\text{cost}(v,x)$$$ for all $$$1 \le v,x \le 1000$$$ takes around $$$O(1000^2).$$$

In the main DP, for each right endpoint $$$i$$$ we extend the segment leftwards. For a segment $$$[l,i]$$$, the number of candidate values is at most $$$\min(a_l,\dots,a_i)$$$. Hence the total number of updates is bounded by

$$$\sum_{i=1}^{n} \sum_{l=1}^{i} \min(a_l,\dots,a_i)$$$ $$$\;\le\;$$$ $$$\sum_{i=1}^{n} \sum_{l=1}^{i} a_l$$$ $$$\;\le\;$$$ $$$n \sum_{i=1}^{n} a_i = nS,$$$ which is $$$O(nS)$$$. where $$$S = \sum_{i=1}^{n} a_i \le 100n$$$.

Therefore, the overall time complexity is $$$\boxed{O(1000^2 + nS)}.$$$

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1010;
const int INF = 1e9;

int dp[MAX + 10][MAX + 10];
vector<int> pfactor[MAX + 10];

/*
 dp[i][j] = minimum operations required to convert j -> i
*/
void pre() {
    // compute proper divisors
    for (int i = 1; i <= MAX; i++) {
        int val = i;
        for (int j = 2; j * j <= val; j++) {
            if (val % j == 0) {
                pfactor[i].push_back(j);
                if (val != j * j) pfactor[i].push_back(val / j);
            }
        }
    }

    // initialize dp table
    for (int i = 0; i <= MAX; i++) {
        for (int j = 0; j <= MAX; j++) {
            dp[i][j] = INF;
        }
        dp[i][i] = 0;
    }

    // compute dp using division and decrement transitions
    for (int i = 1; i <= MAX; i++) {
        int mn = INF;
        for (int j = i; j <= MAX; j++) {
            for (int k : pfactor[j]) {
                dp[i][j] = min(dp[i][j], dp[i][k] + 1);
            }
            dp[i][j] = min(dp[i][j], j + mn);
            mn = min(mn, dp[i][j] - j);
        }
    }
}

void solve() {
    int n, k;
    cin >> n >> k;

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

    // large k shortcut
    if (k >= 3 * n) {
        cout << n - 1 << '\n';
        return;
    }

    // oper[i][j] = cost to convert a[0..j-1] into value i
    int oper[MAX + 10][n + 1];
    memset(oper, 0, sizeof(oper));

    for (int i = 1; i <= MAX; i++) {
        for (int j = 1; j <= n; j++) {
            oper[i][j] = oper[i][j - 1] + dp[i][a[j - 1]];
        }
    }

    // fdp[i][j] = minimum segments covering [1..i] using j operations
    int fdp[n + 1][k + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            fdp[i][j] = INF;
        }
    }

    // base case
    for (int j = 0; j <= k; j++) {
        fdp[0][j] = 0;
    }

    // main DP
    for (int i = 1; i <= n; i++) {
        int mn = a[i - 1];

        for (int j = i; j >= 1; j--) {
            mn = min(mn, a[j - 1]);

            int operations = INF;
            for (int p = 1; p <= mn; p++) {
                int s = oper[p][i] - oper[p][j - 1];
                operations = min(operations, s);
            }

            for (int p = operations; p <= k; p++) {
                fdp[i][p] = min(fdp[i][p],
                                fdp[j - 1][p - operations] + 1);
            }
        }
    }

    // beauty = n - number of segments
    cout << n - fdp[n][k] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    pre();
    solve();

    return 0;
}

For any query $$$(a, b)$$$, assume $$$a \le b$$$ without loss of generality. There are three possible scenarios for their meeting point $$$P$$$:

$$$1$$$ $$$-$$$ To the Left: $$$P \le a$$$. Both Alice and Bob must choose the "Left" direction.

$$$2$$$ $$$-$$$ To the Right: $$$P \ge b$$$. Both Alice and Bob must choose the "Right" direction.

$$$3$$$ $$$-$$$ In the Middle: $$$a \le P \le b$$$. Alice must choose "Right" and Bob must choose "Left".

The movement rule ("closest mountain strictly higher") defines a functional relationship. For every mountain $$$i$$$, there is at most one mountain to its right that it can jump to, and at most one to its left.Let $$$R[i]$$$ be the index of the first $$$j \gt i$$$ such that $$$H[j] \gt H[i]$$$.Let $$$L[i]$$$ be the index of the first $$$j \lt i$$$ such that $$$H[j] \gt H[i]$$$.These relationships form two forests (one for right jumps, one for left jumps).

If Alice and Bob both move in the same direction (e.g., Right), they will meet at the Lowest Common Ancestor (LCA) of nodes $$$a$$$ and $$$b$$$ in the corresponding jump forest. If they move towards each other, they will meet at the unique maximum peak in the range $$$[a, b]$$$.

To compute the distance (number of moves) between any two mountains $$$u$$$ and $$$v$$$ in these forests, or to find their LCA, we can use Binary Lifting. Since $$$N, Q \le 10^5$$$, an $$$O((N+Q) \log N)$$$ approach is required.

The problem can be solved by modeling the "closest higher mountain" rule as a tree structure and analyzing the three cases for each query.

$$$1.$$$ Preprocessing

We use a Monotonic Stack to find the nearest higher mountain to the left ($$$L[i]$$$) and right ($$$R[i]$$$) for every index $$$i$$$ in $$$O(n)$$$.These pointers define two forests. We add a "virtual root" (index 0 and index $$$n+1$$$) to make them single trees by making h[0] = h[n + 1] = INT_MAX (or any maximum value greter than all values in height array).

After that there is two trees $$$:$$$

$$$1.$$$ by adding edge between i and L[i] denote it as L rooted at $$$0$$$.

$$$2.$$$ by adding edge between i and R[i] denote it as R rooted at $$$n + 1$$$.

We precompute Binary Lifting tables and the depth of each node in both trees.

We build a Sparse Table to answer Range Maximum Queries (RMQ), returning the index of the maximum element.

$$$2.$$$ Handling Queries

For each query $$$(a, b)$$$, assume $$$a \le b$$$. We check three scenarios:

Case 1: Both move Left.

They meet at $$$P = \text{LCA}_L(a, b)$$$.

$$$\text{Effort} = \text{dist}_L(a, P) + \text{dist}_L(b, P)$$$.

if $$$P$$$ $$$= 0$$$ then invalid.

Case 2: Both move Right.

They meet at $$$P = \text{LCA}_R(a, b)$$$.

$$$\text{Effort} = \text{dist}_R(a, P) + \text{dist}_R(b, P)$$$.

if $$$P$$$ $$$=$$$ $$$n + 1$$$ then invalid.

Case 3: Moving Towards Each Other.

They meet at $$$M = \text{RMQ_index}(a, b)$$$(index of maximum value in $$$[a , b]$$$).

Alice can reach $$$M$$$ if $$$\text{dist}_R(a, M)$$$ is valid.Bob can reach $$$M$$$ if $$$\text{dist}_L(b, M)$$$ is valid.

$$$\text{Effort} = \text{dist}_R(a, M) + \text{dist}_L(b, M)$$$.

The answer is the minimum effort across all valid cases. If no case is valid, output $$$-1$$$.

Time Complexity: $$$O(N \log N)$$$ for preprocessing (Sparse Table + Binary Lifting) and $$$O(Q \log N)$$$ for queries.

Memory: $$$O(N \log N)$$$ to store the lifting tables and sparse table.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int LOGN = 19;
const int INF = 1e9;

int n, q;
int h[MAXN];
int upL[MAXN][LOGN], upR[MAXN][LOGN];
int depL[MAXN], depR[MAXN];
pair<int, int> st[MAXN][LOGN]; // Stores {height, index} for RMQ

// Function to get the index of the mountain with the maximum height in range [l, r]
int query_max_idx(int l, int r) {
    if (l > r) swap(l, r);
    int k = 31 - __builtin_clz(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]).second;
}

// Binary lifting to find LCA in a given tree
int get_lca(int u, int v, int up[MAXN][LOGN], int dep[]) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LOGN - 1; i >= 0; i--) {
        if (dep[u] - (1 << i) >= dep[v]) u = up[u][i];
    }
    if (u == v) return u;
    for (int i = LOGN - 1; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

// Function to calculate jump distance between two nodes in the tree
int get_dist(int u, int target, int up[MAXN][LOGN], int dep[]) {
    if (u == target) return 0;
    if (u == -1 || target == -1) return INF;
    int curr = u, dist = 0;
    for (int i = LOGN - 1; i >= 0; i--) {
        if (dep[curr] - (1 << i) >= dep[target] && up[curr][i] != -1) {
            curr = up[curr][i];
            dist += (1 << i);
        }
    }
    return (curr == target) ? dist : INF;
}

void solve() {
    
    cin >> n;
    // Define sentinel heights for virtual roots (0 and n+1)
    h[0] = h[n + 1] = 2e9; 
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        st[i][0] = {h[i], i};
    }

    // 1. Build Sparse Table for Range Maximum Query
    for (int j = 1; j < LOGN; 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]);
        }
    }

    // 2. Build Tree Parent Pointers using Monotonic Stack
    stack<int> s;
    s.push(0); // Left Tree root
    for (int i = 1; i <= n; i++) {
        while (h[s.top()] <= h[i]) s.pop();
        upL[i][0] = s.top();
        s.push(i);
    }
    
    while (!s.empty()) s.pop();
    s.push(n + 1); // Right Tree root
    for (int i = n; i >= 1; i--) {
        while (h[s.top()] <= h[i]) s.pop();
        upR[i][0] = s.top();
        s.push(i);
    }

    // 3. Precompute Binary Lifting Tables (Ancestors)
    upL[0][0] = -1;
    upR[n + 1][0] = -1;
    for (int j = 1; j < LOGN; j++) {
        for (int i = 0; i <= n + 1; i++) {
            // Left Tree lifting
            if (i <= n && upL[i][j - 1] != -1) upL[i][j] = upL[upL[i][j - 1]][j - 1];
            else if (i <= n) upL[i][j] = -1;
            
            // Right Tree lifting
            if (i >= 1 && upR[i][j - 1] != -1) upR[i][j] = upR[upR[i][j - 1]][j - 1];
            else if (i >= 1) upR[i][j] = -1;
        }
    }

    // 4. Calculate Depths for LCA functionality
    auto build_depth = [&](int root, int up[MAXN][LOGN], int dep[]) {
        vector<vector<int>> adj(n + 2);
        for (int i = 0; i <= n + 1; i++) {
            if (i != root && up[i][0] != -1) adj[up[i][0]].push_back(i);
        }
        function<void(int, int)> dfs = [&](int u, int d) {
            dep[u] = d;
            for (int v : adj[u]) dfs(v, d + 1);
        };
        dfs(root, 0);
    };
    build_depth(0, upL, depL);
    build_depth(n + 1, upR, depR);

    // 5. Process Queries
    cin >> q;
    while (q--) {
        int a, b; cin >> a >> b;
        //Swap so a is always the left index and b is the right index
        if (a > b) swap(a, b);

        int min_effort = INF;

        // Case 1: Alice and Bob both choose to move LEFT
        int lcl = get_lca(a, b, upL, depL);
        if (lcl != 0) { // Must not meet at the virtual root
            int d = get_dist(a, lcl, upL, depL) + get_dist(b, lcl, upL, depL);
            min_effort = min(min_effort, d);
        }

        // Case 2: Alice and Bob both choose to move RIGHT
        int rcl = get_lca(a, b, upR, depR);
        if (rcl != n + 1) { // Must not meet at the virtual root
            int d = get_dist(a, rcl, upR, depR) + get_dist(b, rcl, upR, depR);
            min_effort = min(min_effort, d);
        }

        // Case 3: Alice moves RIGHT and Bob moves LEFT (meeting in the middle)
        int peak = query_max_idx(a, b);
        int d_alice = get_dist(a, peak, upR, depR);
        int d_bob = get_dist(b, peak, upL, depL);
        if (d_alice != INF && d_bob != INF) {
            min_effort = min(min_effort, d_alice + d_bob);
        }

        cout << (min_effort >= INF ? -1 : min_effort) << " ";
    }
    cout << endl;
}

int main() {
  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

For simplicity, assume $$$a \le b$$$. Given $$$H[i]$$$ as the height of the $$$i$$$-th mountain, there are three regions where Alice and Bob can meet:

Case $$$1: $$$Between $$$a$$$ and $$$b$$$, i.e., $$$[a, b]$$$.

Case $$$1: $$$To the left of $$$a$$$, i.e., $$$[1, a]$$$.

Case $$$1: $$$To the right of $$$b$$$, i.e., $$$[b, n]$$$.

Fix their directions according to these three cases.

If they meet within the range $$$[a, b]$$$, they will necessarily meet at the index $$$i$$$ where $$$H[i]$$$ is the maximum value in the subarray from index $$$a$$$ to $$$b$$$.

Try to solve this sub-problem: if you are given an index $$$i$$$, and you can only move from $$$i$$$ to the minimum index $$$j$$$ such that $$$j \gt i$$$ and $$$H[j] \gt H[i]$$$ (the next greater element), at what index will you arrive after $$$x$$$ moves?

Try to come up with a fast approach.

You can solve the above problem in $$$O(\log N)$$$ for every value of $$$(i, x)$$$ using binary jumping.

Learn more about this technique here: https://usaco.guide/plat/binary-jump

For any index $$$i$$$ in the range $$$[1, a]$$$, if they can meet at index $$$i$$$, they could also potentially meet at any index $$$j$$$ that is reachable from $$$i$$$ (where $$$j$$$ is a higher mountain further in that direction). The same logic applies to the third case (to the right of $$$b$$$).

Notation:

$$$F_aL(x)$$$: The index Alice reaches after $$$x$$$ moves to the Left starting from $$$a$$$.

$$$F_bL(x)$$$: The index Bob reaches after $$$x$$$ moves to the Left starting from $$$b$$$.

$$$F_aR(x)$$$: The index Alice reaches after $$$x$$$ moves to the Right starting from $$$a$$$.

$$$F_bR(x)$$$: The index Bob reaches after $$$x$$$ moves to the Right starting from $$$b$$$.

Precomputation:Using binary jumping, precompute two tables ($$$1 \le i \le n$$$ and $$$0 \le j \le \log n$$$):

pre[i][j]: The index reached starting from $$$i$$$ after $$$2^j$$$ moves to the Left.

suf[i][j]: The index reached starting from $$$i$$$ after $$$2^j$$$ moves to the Right.

Case 1: Meeting between $$$[a, b]$$$

Alice and Bob must meet at the index $$$M$$$ containing the maximum value in the range $$$[a, b]$$$.If there are multiple identical maximum values, they will never meet (as they always jump to the closest higher peak).Otherwise, let $$$M$$$ be the index of the unique maximum. Calculate the number of moves $$$x_a$$$ Alice needs to reach $$$M$$$ moving Right ($$$F_aR(x_a) = M$$$) and the number of moves $$$x_b$$$ Bob needs to reach $$$M$$$ moving Left ($$$F_bL(x_b) = M$$$).

The total effort is $$$x_a + x_b$$$.

Case 2: Meeting to the Left $$$[1, a]$$$

Define a function $$$F(x_a, x_b) = \text{true}$$$ if $$$F_aL(x_a) = F_bL(x_b)$$$, and $$$\text{false}$$$ otherwise.

Monotonicity: If $$$F(x_a, x_b)$$$ is true, then $$$F(x_a + 1, x_b + 1)$$$ is also true. This is because once they meet at a peak, any further move in the same direction will lead them to the same next higher peak.

Then we can Binary search for the smallest $$$x_a$$$. For any chosen $$$x_a$$$, determine if there exists an $$$x_b$$$ such that $$$F_aL(x_a) = F_bL(x_b)$$$.If a match is found, try searching for a smaller $$$x$$$ ($$$x \lt x_a$$$); if not, search for a larger $$$x$$$ ($$$x \gt x_a$$$).

Minimizing $$$x_a$$$ will inherently minimize $$$x_b$$$, thus minimizing the total effort $$$(x_a + x_b)$$$. Use the pre array to calculate positions efficiently.

Case 3: Meeting to the Right $$$[b, n]$$$

This follows the same logic as Case 2. Binary search for the smallest $$$x_b$$$ such that a corresponding $$$x_a$$$ exists. Use the suf array to calculate positions.

Final_Ans: For each query, the answer is the minimum effort among the three cases. If no meeting point is found in any case, output $$$-1$$$.

Time Complexity: $$$O(n \log n)$$$ for precomputation + $$$O(q \log^2 n)$$$ for answering queries.

#include<bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)




const int N = 100005 ;
const int M = 19 ;
int a[N] ;
int pre[N][M] ;
int suf[N][M] ;

void init() {
  for(int i = 0 ; i < N ; i ++) {
    for(int j = 0 ; j < M ; j ++) {
      pre[i][j] = suf[i][j] = -1 ;
    }
  }
}
 

void solve() {
  
        init() ;
  
        int n ;
        cin >> n ;
        for(int i = 0 ; i < n ; i ++) cin >> a[i] ;
        stack <int> st ;
        for(int i = 0 ; i < n ; i ++) {
          while(!st.empty() && a[st.top()] <= a[i]) st.pop() ;
          if(!st.empty()) pre[i][0] = st.top() ;
          st.push(i) ;
        }
        while(!st.empty()) st.pop() ;
        for(int i = n - 1 ; i >= 0 ; i --) {
          while(!st.empty() && a[st.top()] <= a[i]) st.pop() ;
          if(!st.empty()) suf[i][0] = st.top() ;
          st.push(i) ;
        }
        for(int b = 1 ; b < M ; b ++) {
          for(int i = 0 ; i < n ; i ++) {
            
            if(pre[i][b - 1] != -1) pre[i][b] = pre[pre[i][b - 1]][b - 1] ;
            if(suf[i][b - 1] != -1) suf[i][b] = suf[suf[i][b - 1]][b - 1] ;
            
          }
        }
        
        int q ;
        cin >> q ;
        while(q --) {
          int a , b ;
          cin >> a >> b ;
          a -- ;
          b -- ;
          if(a > b) swap(a , b) ;
          
          int ans = 2 * n + 1 ;
          // to the left of a 
          
          int L = 0 ;
          int R = n ;
          while(L <= R) {
            
            int mid = (L + R) / 2 ;
            int ia = a ;
            for(int i = M - 1 ; i >= 0 ; i --) {
              if(ia == -1) break ;
              if(mid & (1LL << i)) ia = pre[ia][i] ;
            }
            if(ia == -1) {
              R = mid - 1 ;
              continue ;
            }
            
            
            int ib = b ;
            int steps = 0 ;
            for(int i = M - 1 ; i >= 0 ; i --) {
              if(pre[ib][i] == -1) continue ;
              if(pre[ib][i] >= ia) {
                steps += (1LL << i) ;
                ib = pre[ib][i] ;
              }
            }
            
            if(ib == ia) {
              ans = min(ans , mid + steps) ;
              R = mid - 1 ;
            } else L = mid + 1 ;
            
            
            
          }
          
          
          // to the right of b 
          
          L = 0 ;
          R = n ;
          while(L <= R) {
            
            int mid = (L + R) / 2 ;
            int ib = b ;
            for(int i = M - 1 ; i >= 0 ; i --) {
              if(ib == -1) break ;
              if(mid & (1LL << i)) ib = suf[ib][i] ;
            }
            if(ib == -1) {
              R = mid - 1 ;
              continue ;
            }
          
            int ia = a ;
            int steps = 0 ;
            for(int i = M - 1 ; i >= 0 ; i --) {
              if(suf[ia][i] == -1) continue ;
              if(suf[ia][i] <= ib) {
                steps += (1LL << i) ;
                ia = suf[ia][i] ;
              }
            }
            
            if(ib == ia) {
              ans = min(ans , mid + steps) ;
              R = mid - 1 ;
            } else L = mid + 1 ;
            
            
            
          }
          
          
          
          // in mid or on a or on b 
          
          // always meet at max[a , b] 
          
          int ia = a ;
          int steps = 0 ;
          for(int i = M - 1 ; i >= 0 ; i --) {
            if(suf[ia][i] == -1) continue ;
            if(suf[ia][i] <= b) {
              ia = suf[ia][i] ;
              steps += (1LL << i) ;
            }
          }
          
          int ib = b ;
          for(int i = M - 1 ; i >= 0 ; i --) {
            if(pre[ib][i] == -1) continue ;
            if(pre[ib][i] >= ia) {
              ib = pre[ib][i] ;
              steps += (1LL << i) ;
            }
          }
          if(ia == ib) ans = min(ans , steps) ;
          if(ans > 2 * n) ans = -1 ;
          
          cout << ans << " " ;
          
          
        }
        
        
        
        
        
}




int32_t main() {

    fastio();
    
    int t{1};
    //cin >> t;
    while (t--) {
        solve() ;
    }

}