#include "walk.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i =k; i<n; i++)
#define vi vector<int>
#define pii pair<int,int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vpii vector<pii>
#define mii map<int,int>
#define dout(x) cout<<x<<' '<<#x<<endl;
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl;
#define out(x) cout<<x<<endl;
#define out2(x,y) cout<<x<<' '<<y<<endl;
using namespace std;
const int mxn = 1e5 + 5;
map<int, vpii> adj;
int min_distance(vector<signed> x, vector<signed> h, vector<signed> l, vector<signed> r, vector<signed> y, signed s, signed g) {
//encode a position as h * n + i
int n = x.size();
int m = l.size();
vvi ints(n);
f0r(i,m){
for(int j = l[i]; j<=r[i]; j++){
if(h[j] >= y[i])ints[j].pb(y[i] * n + j);
}
for(int j = l[i]; j<r[i]; j++){
adj[y[i] * n + j].pb(mp(y[i] * n + j + 1, x[j+1] - x[j]));
adj[y[i] * n + j + 1].pb(mp(y[i] * n + j, x[j+1] - x[j]));
}
}
f0r(i,n){
ints[i].pb(i);
}
f0r(i,n){
sort(ints[i].begin(), ints[i].end());
}
f0r(i,n){
f0r(j, ints[i].size() - 1){
int h1 = ints[i][j] / n;
int h2 = ints[i][j+1] / n;
adj[ints[i][j]].pb(mp(ints[i][j+1], h2-h1));
adj[ints[i][j+1]].pb(mp(ints[i][j], h2-h1));
}
}
mii dist;
dist[s] = 0;
priority_queue<pii>q;
q.push(mp(0,s));
while(!q.empty()){
int node = q.top().second;
q.pop();
for(auto u : adj[node]){
int b = u.first;
int w = u.second;
if(!dist.count(b) || dist[b] > dist[node] + w){
dist[b] = dist[node] + w;
q.push(mp(-dist[b], b));
}
}
}
/*
out(dist[n + 1]);
out(dist[6 * n + 1]);
out(dist[6 * n + 2]);
out(dist[7*n+2]);
out(dist[7*n+6]);
out(dist[5*n+6]);
out(dist[5*n+5]);
*/
if(!dist.count(g))return -1;
else return dist[g];
return 1;
}
