// Oh damn! Suddenly you're free to fly...
#include<bits/stdc++.h>
#include "railroad.h"
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 4e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 10;
int pr[maxn];
int fnd(int u){
return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
bool mrg(int a, int b){
if( (a = fnd(a)) == (b = fnd(b)) )
return 0;
if(pr[a] > pr[b])
swap(a, b);
pr[a]+= pr[b];
pr[b] = a;
return 1;
}
ll plan_roller_coaster(vector<int> a, vector<int> b){
memset(pr, -1, sizeof pr);
int n = sz(a);
map<int, int> mp;
mp[0]++; // first of all
for(int x : a)
mp[x]--;
for(int x : b)
mp[x]++;
vector<int> tot;
for(int x : a)
tot.PB(x);
for(int x : b)
tot.PB(x);
sort(tot.begin(), tot.end());
tot.resize( unique(tot.begin(), tot.end()) - tot.begin() );
auto comp = [&](int x){
return lower_bound(tot.begin(), tot.end(), x) - tot.begin() + 1;
};
int mrgs = 0;
for(int i = 0; i < n; i++){
mrgs+= mrg(comp(a[i]), comp(b[i]));
}
int sum = 0, ID = 0;
for(auto it = mp.begin(); it != mp.end(); it++, ID++){
sum+= it->S;
if(sum < 0)
return 10;
if(sum > 0)
mrgs+= mrg(ID, ID + 1);
}
if(mrgs != sz(tot) + 2 - 1)
return 9;
return 0;
}
