By Francisco Elio Parente Arcos Filho, UEA Brazil
A parkour practitioner intends to make a video with several maneuvers where he will jump between several buildings in an ever-increasing trajectory, that is, he will always jump from one building to another that has greater height.
Although dangerous is something that attracts attention in sport, this sportsman does not intend to take any more risks than necessary.He intends to make his way from the building he chooses to start to the largest building he can ever jump to the nearest option on the left or right.
In other words, since Hi is the height of i-th building from the beginning of the street, he can jump from building i to building j if Hi < Hj and there is no building k such that Hi < Hk and i < k < j or j < k < i.
Your task is to determine how many different paths there are to make this video.
The description of the street where it will be filmed, the height of each building and its distance from the beginning of the street will be provided.
The traceur (person who practices parkour) can start in any of the buildings.
The first line of input consists of a integer N (1 ≤ N ≤ 106), the number os buildings in the street.
The following N lines each consists of two integers: H (1 ≤ H ≤ 109) and X (1 ≤ X ≤ 109), that indicate the height of a building and its distance from the beginning of the street, respectively.
Input Samples | Output Samples |
4 |
7 |
6 |
15 |
9 |
14 |