ZeptoLab Code Rush 2015 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

divide and conquer

*3000

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Pudding Monsters

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIn 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?).

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 × 10^{5}) — 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 *r*_{i}, *c*_{i} (1 ≤ *r*_{i}, *c*_{i} ≤ *n*) — the row number and the column number of the cell that initially contains the *i*-th monster.

It is guaranteed that all *r*_{i} are distinct numbers and all *c*_{i} 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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/30/2023 06:47:58 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|