#include <bits/stdc++.h>
using namespace std;
struct Event {
int time, box_id;
bool is_remove;
const bool operator<(const Event &other) {
return time < other.time;
}
};
const int MAXN = 1'000'001;
const int MOD = 1'000'000'007;
int n;
int A[MAXN], B[MAXN];
vector<Event> events;
int dfs(int cur_time, vector<int> &left_stack, vector<int> &right_stack) {
int our_box = events[cur_time].box_id;
bool remove = events[cur_time].is_remove;
if (remove && !(left_stack.back() == our_box || right_stack.back() == our_box)) {
return 0;
}
int ways = 0;
if (cur_time >= 2*n-1) {
ways = remove ? 1: 0;
return ways;
}
if (remove ) {
bool is_left = false;
if (left_stack.back() == our_box) {
left_stack.pop_back();
is_left = true;
} else {
right_stack.pop_back();
}
ways += dfs(cur_time + 1, left_stack, right_stack);
(is_left ? left_stack : right_stack).push_back(our_box);
} else {
left_stack.push_back(our_box);
ways += dfs(cur_time + 1, left_stack, right_stack);
left_stack.pop_back();
right_stack.push_back(our_box);
ways += dfs(cur_time + 1, left_stack, right_stack);
right_stack.pop_back();
}
return ways;
}
void brute() {
vector<int> ls(1, -1), rs(1, -1);
cout << dfs(0, ls, rs);
}
void solve() {
int ways = 0;
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> as, bs;
bool valid = true;
for (auto &event : events) {
bool left = mask & (1 << (event.box_id));
if (event.is_remove && (left ? as : bs).back() != event.box_id) {
valid = false;
break;
} else if (event.is_remove) {
(left ? as : bs).pop_back();
} else {
(left ? as : bs).push_back(event.box_id);
}
}
if (valid) ways++;
}
cout << ways;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> A[i] >> B[i];
}
for (int i = 0; i < n; i++) {
events.push_back(Event {A[i], i, false});
events.push_back(Event {B[i], i, true});
}
sort(events.begin(), events.end());
solve();
return 0;
}
