#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 1e5 + 5;
const int inf = 1e9 + 7;
vector<int> edges[N], pos[N];
int a[N], par[N][20], path[N][20][2][2], p[N];
int st[N][20], tin[N], tout[N], t;
int L[N], R[N], ver[N], sz[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, k, q; cin>>n>>k>>q;
for(int i=0;i<n;i++){
cin>>a[i];
st[i][0] = a[i];
pos[a[i]].push_back(i);
}
for(int j=1;j<20;j++){
for(int i=0;i+(1 << (j - 1)) < n;i++){
st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j-1]);
}
}
auto ger = [&](int l, int r){
int lg = __lg(r - l + 1);
return max(st[l][lg], st[r - (1 << lg) + 1][lg]);
};
int last = 1;
function<void(int, int, int)> get = [&](int l, int r, int u){
//~ cout<<l<<" "<<r<<" "<<u<<"\n";
tin[u] = ++t;
for(int j=1;j<20;j++){
par[u][j] = par[par[u][j-1]][j-1];
//~ if(par[u][j-1]){
//~ cout<<par[u][j-1]<<" "<<par[par[u][j-1]][j-1]<<"\n";
//~ }
for(int t=0;t<2;t++){
for(int k=0;k<2;k++){
if(u) path[u][j][t][k] = inf;
for(int l=0;l<2;l++){
path[u][j][t][k] = min(path[u][j][t][k], path[u][j-1][t][l] + path[par[u][j-1]][j-1][l][k]);
}
}
}
}
if(l + 1 >= r){
tout[u] = t;
return;
}
int mx = ger(l + 1, r - 1);
int i = upper_bound(pos[mx].begin(), pos[mx].end(), l) - pos[mx].begin();
int lx = l, P = 0;
for(;i<(int)pos[mx].size() && pos[mx][i] < r;i++){
int j = pos[mx][i];
ver[j] = last;
edges[u].push_back(last);
p[last] = P++;
L[last] = lx, R[last] = j;
last++, lx = j;
}
edges[u].push_back(last);
p[last] = P++;
sz[u] = P, L[last] = lx, R[last] = r;
last++;
for(auto x : edges[u]){
par[x][0] = u;
path[x][0][0][0] = min(p[x], sz[u] - p[x] + 1);
path[x][0][1][1] = min(p[x] + 2, sz[u] - p[x] - 1);
path[x][0][0][1] = path[x][0][1][0] = min(p[x] + 1, sz[u] - p[x]);
get(L[x], R[x], x);
}
tout[u] = t;
};
get(-1, n, 0);
//~ for(int i=1;i<last;i++){
//~ for(int j=0;j<3;j++){
//~ cout<<par[i][j]<<" ";
//~ } cout<<"\n";
//~ }
auto is = [&](int a, int b){
return (tin[a] <= tin[b] && tin[b] <= tout[a]);
};
auto gg = [&](ar<int, 2>& d, int a, int b){
for(int j=19;~j;j--){
if(!is(par[b][j], a)){
ar<int, 2> T {};
//~ cout<<d[0]<<" "<<d[1]<<" "<<par[b][j]<<"\n";
T[0] = min(d[0] + path[b][j][0][0], d[1] + path[b][j][1][0]);
T[1] = min(d[0] + path[b][j][0][1], d[1] + path[b][j][1][1]);
swap(T, d);
b = par[b][j];
}
}
return b;
};
//~ cout<<ver[0]<<"\n";
auto check = [&](int a, int ta, int b, int tb){
int res = inf;
if(a == b) return 1ll;
//~ cout<<a<<" "<<b<<"\n";
if(is(b, a)) swap(a, b), swap(tb, ta);
if(is(a, b)){
ar<int, 2> d {}; d[!tb]++;
int v = gg(d, a, b);
//~ cout<<d[0]<<" "<<d[1]<<" <-\n";
ar<int, 2> T {};
T[0] = min(d[0] + path[v][0][0][0], d[1] + path[v][0][1][0]);
T[1] = min(d[0] + path[v][0][0][1], d[1] + path[v][0][1][1]);
return T[ta];
}
//~ cout<<a<<" "<<b<<"\n";
ar<int, 2> d1 {}, d2 {};
d1[!ta]++; d2[!tb]++;
int v1 = gg(d1, b, a);
int v2 = gg(d2, a, b);
//~ cout<<d1[0]<<" "<<d1[1]<<"\n";
//~ cout<<d2[0]<<" "<<d2[1]<<"\n";
for(int t=0;t<2;t++){
for(int k=0;k<2;k++){
int bet = abs(p[v1] + t - p[v2] - k);
bet = min({bet, path[v1][0][t][0] + path[v2][0][k][0], path[v1][0][t][1] + path[v2][0][k][1]});
//~ cout<<t<<" "<<k<<" "<<d1[t]<<" "<<d2[k]<<" "<<bet<<"\n";
res = min(res, d1[t] + d2[k] + bet);
}
}
//~ cout<<"\n";
return res;
};
while(q--){
int i, j; cin>>i>>j;
i--, j--;
int res = inf;
for(int t=0;t<2;t++){
for(int k=0;k<2;k++){
//~ int x = check(ver[i] + t, !t, ver[j] + k, !k);
//~ cout<<x<<"\n";
//~ res = min(res, x);
res = min(res, check(ver[i] + t, !t, ver[j] + k, !k));
//~ cout<<check(ver[i] + t, !t, ver[j] + k, !k)<<"\n";
}
}
cout<<res - 1<<"\n";
//~ cout<<"\n";
}
}
/*
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
5 4 1 2 3 1 1 2 4 5 4 1 5 3 5
15 5 2
5
4
1
2
3
1
1
2
4
5
4
1
5
3
5
8 1
5 3
2
1
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5156 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5164 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 8 |
Correct |
3 ms |
5204 KB |
Output is correct |
| 9 |
Correct |
3 ms |
5028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6868 KB |
Output is correct |
| 2 |
Runtime error |
190 ms |
211296 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
194 ms |
213052 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
205 ms |
220508 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
