#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(Ofast)
using namespace std;
inline long long read() {
  register long long x = 0, f = 1;
  register char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c & 15);
  return x * f;
}
template <class T>
inline bool cmax(T& x, T y) {
  return x > y ? 1 : x = y, 0;
}
template <class T>
inline bool cmin(T& x, T y) {
  return x < y ? 1 : x = y, 0;
}
const long long MAXN = 3e5 + 10;
const long long mod7 = 1e9 + 7;
const long long mod9 = 1e9 + 9;
const long long mod = 998244353;
inline long long QP(long long x, long long y, long long Mod) {
  long long ans = 1;
  for (; y; y >>= 1, x = (x * x) % Mod)
    if (y & 1) ans = (ans * x) % Mod;
  return ans;
}
long long n, m;
vector<long long> v;
long long a[MAXN];
inline void io() {
  ios ::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
}
long long mn[MAXN << 2];
long long len[MAXN << 2];
long long tag[MAXN << 2];
inline void Push_Up(long long rt) {
  mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
  if (mn[rt << 1] == mn[rt << 1 | 1])
    len[rt] = len[rt << 1] + len[rt << 1 | 1];
  else {
    if (mn[rt] == mn[rt << 1])
      len[rt] = len[rt << 1];
    else
      len[rt] = len[rt << 1 | 1];
  }
}
inline void build(long long l, long long r, long long rt) {
  mn[rt] = 0;
  len[rt] = r - l + 1;
  if (l == r) return;
  long long mid = l + r >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
}
inline void Push_down(long long rt) {
  if (!tag[rt]) return;
  tag[rt << 1] += tag[rt];
  tag[rt << 1 | 1] += tag[rt];
  mn[rt << 1] += tag[rt];
  mn[rt << 1 | 1] += tag[rt];
  tag[rt] = 0;
}
inline void Upd(long long a, long long b, long long l, long long r,
                long long rt, long long val) {
  if (a <= l && r <= b) {
    mn[rt] += val;
    tag[rt] += val;
    return;
  }
  Push_down(rt);
  long long mid = l + r >> 1;
  if (a <= mid) Upd(a, b, l, mid, rt << 1, val);
  if (b > mid) Upd(a, b, mid + 1, r, rt << 1 | 1, val);
  Push_Up(rt);
}
inline pair<long long, long long> Query(long long a, long long b, long long l,
                                        long long r, long long rt) {
  if (a <= l && r <= b) {
    return make_pair(mn[rt], len[rt]);
  }
  Push_down(rt);
  long long mid = l + r >> 1;
  pair<long long, long long> ans1 = make_pair(INT_MAX, 0);
  pair<long long, long long> ans2 = make_pair(INT_MAX, 0);
  if (a <= mid) ans1 = Query(a, b, l, mid, rt << 1);
  if (b > mid) ans2 = Query(a, b, mid + 1, r, rt << 1 | 1);
  pair<long long, long long> ans;
  if (ans1.first == ans2.first) {
    ans = make_pair(ans1.first, ans1.second + ans2.second);
    return ans;
  }
  if (ans1.first < ans2.first) {
    ans = ans1;
    return ans;
  } else {
    ans = ans2;
    return ans;
  }
  return ans;
}
pair<long long, long long> mxs[MAXN], mns[MAXN];
map<long long, long long> _mp;
signed main() {
  n = read();
  for (register long long i = 1; i <= n; i++) {
    long long x = read();
    a[x] = read();
  }
  long long ans = 0;
  _mp.clear();
  build(1, n, 1);
  long long maxs = 0, mins = 0;
  for (register long long i = 1; i <= n; i++) {
    while (maxs > 0 && mxs[maxs].first < a[i]) {
      Upd(mxs[maxs - 1].second + 1, mxs[maxs].second, 1, n, 1,
          a[i] - mxs[maxs].first);
      maxs--;
    }
    mxs[++maxs] = make_pair(a[i], i);
    while (mins > 0 && mns[mins].first > a[i]) {
      Upd(mns[mins - 1].second + 1, mns[mins].second, 1, n, 1,
          mns[mins].first - a[i]);
      mins--;
    }
    mns[++mins] = make_pair(a[i], i);
    Upd(_mp[a[i]] + 1, i, 1, n, 1, -1);
    _mp[a[i]] = i;
    pair<long long, long long> flg = Query(1, i, 1, n, 1);
    if (flg.first == -1) ans += flg.second;
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Please formulate a cpp solution to the following problem:

In this problem you will meet the simplified model of game Pudding Monsters.

An important process in developing any game is creating levels. A game field in Pudding Monsters is an n × n rectangular grid, n of its cells contain monsters and some other cells contain game objects. The gameplay is about moving the monsters around the field. When two monsters are touching each other, they glue together into a single big one (as they are from pudding, remember?).

<image>

Statistics showed that the most interesting maps appear if initially each row and each column contains exactly one monster and the rest of map specifics is set up by the correct positioning of the other game objects. 

A technique that's widely used to make the development process more efficient is reusing the available resources. For example, if there is a large n × n map, you can choose in it a smaller k × k square part, containing exactly k monsters and suggest it as a simplified version of the original map.

You wonder how many ways there are to choose in the initial map a k × k (1 ≤ k ≤ n) square fragment, containing exactly k pudding monsters. Calculate this number.

Input

The first line contains a single integer n (1 ≤ n ≤ 3 × 105) — the size of the initial field.

Next n lines contain the coordinates of the cells initially containing monsters. The i-th of the next lines contains two numbers ri, ci (1 ≤ ri, ci ≤ n) — the row number and the column number of the cell that initially contains the i-th monster.

It is guaranteed that all ri are distinct numbers and all ci are distinct numbers.

Output

Print the number of distinct square fragments of the original field that can form a new map.

Examples

Input

5
1 1
4 3
3 2
2 4
5 5


Output

10

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(Ofast)
using namespace std;
inline long long read() {
  register long long x = 0, f = 1;
  register char c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c & 15);
  return x * f;
}
template <class T>
inline bool cmax(T& x, T y) {
  return x > y ? 1 : x = y, 0;
}
template <class T>
inline bool cmin(T& x, T y) {
  return x < y ? 1 : x = y, 0;
}
const long long MAXN = 3e5 + 10;
const long long mod7 = 1e9 + 7;
const long long mod9 = 1e9 + 9;
const long long mod = 998244353;
inline long long QP(long long x, long long y, long long Mod) {
  long long ans = 1;
  for (; y; y >>= 1, x = (x * x) % Mod)
    if (y & 1) ans = (ans * x) % Mod;
  return ans;
}
long long n, m;
vector<long long> v;
long long a[MAXN];
inline void io() {
  ios ::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
}
long long mn[MAXN << 2];
long long len[MAXN << 2];
long long tag[MAXN << 2];
inline void Push_Up(long long rt) {
  mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
  if (mn[rt << 1] == mn[rt << 1 | 1])
    len[rt] = len[rt << 1] + len[rt << 1 | 1];
  else {
    if (mn[rt] == mn[rt << 1])
      len[rt] = len[rt << 1];
    else
      len[rt] = len[rt << 1 | 1];
  }
}
inline void build(long long l, long long r, long long rt) {
  mn[rt] = 0;
  len[rt] = r - l + 1;
  if (l == r) return;
  long long mid = l + r >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
}
inline void Push_down(long long rt) {
  if (!tag[rt]) return;
  tag[rt << 1] += tag[rt];
  tag[rt << 1 | 1] += tag[rt];
  mn[rt << 1] += tag[rt];
  mn[rt << 1 | 1] += tag[rt];
  tag[rt] = 0;
}
inline void Upd(long long a, long long b, long long l, long long r,
                long long rt, long long val) {
  if (a <= l && r <= b) {
    mn[rt] += val;
    tag[rt] += val;
    return;
  }
  Push_down(rt);
  long long mid = l + r >> 1;
  if (a <= mid) Upd(a, b, l, mid, rt << 1, val);
  if (b > mid) Upd(a, b, mid + 1, r, rt << 1 | 1, val);
  Push_Up(rt);
}
inline pair<long long, long long> Query(long long a, long long b, long long l,
                                        long long r, long long rt) {
  if (a <= l && r <= b) {
    return make_pair(mn[rt], len[rt]);
  }
  Push_down(rt);
  long long mid = l + r >> 1;
  pair<long long, long long> ans1 = make_pair(INT_MAX, 0);
  pair<long long, long long> ans2 = make_pair(INT_MAX, 0);
  if (a <= mid) ans1 = Query(a, b, l, mid, rt << 1);
  if (b > mid) ans2 = Query(a, b, mid + 1, r, rt << 1 | 1);
  pair<long long, long long> ans;
  if (ans1.first == ans2.first) {
    ans = make_pair(ans1.first, ans1.second + ans2.second);
    return ans;
  }
  if (ans1.first < ans2.first) {
    ans = ans1;
    return ans;
  } else {
    ans = ans2;
    return ans;
  }
  return ans;
}
pair<long long, long long> mxs[MAXN], mns[MAXN];
map<long long, long long> _mp;
signed main() {
  n = read();
  for (register long long i = 1; i <= n; i++) {
    long long x = read();
    a[x] = read();
  }
  long long ans = 0;
  _mp.clear();
  build(1, n, 1);
  long long maxs = 0, mins = 0;
  for (register long long i = 1; i <= n; i++) {
    while (maxs > 0 && mxs[maxs].first < a[i]) {
      Upd(mxs[maxs - 1].second + 1, mxs[maxs].second, 1, n, 1,
          a[i] - mxs[maxs].first);
      maxs--;
    }
    mxs[++maxs] = make_pair(a[i], i);
    while (mins > 0 && mns[mins].first > a[i]) {
      Upd(mns[mins - 1].second + 1, mns[mins].second, 1, n, 1,
          mns[mins].first - a[i]);
      mins--;
    }
    mns[++mins] = make_pair(a[i], i);
    Upd(_mp[a[i]] + 1, i, 1, n, 1, -1);
    _mp[a[i]] = i;
    pair<long long, long long> flg = Query(1, i, 1, n, 1);
    if (flg.first == -1) ans += flg.second;
  }
  printf("%lld\n", ans);
  return 0;
}

```