Counting Valid Leader Pairs

Farmer John has (N) cows ((2 \le N \le 10^5)) lined up and numbered from (1) to (N). Each cow has one of two breeds: Guernsey or Holstein. In addition, each cow (i) writes a list that consists of the contiguous range of cows starting from herself (cow (i)) and ending at cow (E_i) (where (i \le E_i \le N)).

Farmer John has discovered that each breed has exactly one leader, but he does not know which cows are the leaders. However, he observes that for each leader, the list that the leader wrote must satisfy at least one of the following conditions:

(\bullet) It includes every cow of the leader's own breed,

(\bullet) It includes the cow that is the leader of the other breed.

More formally, suppose that we decide that cow (g) is the Guernsey leader and cow (h) is the Holstein leader. Then the following must hold:

1. If (g < h): Since cow (h) is after (g), it might lie inside cow (g)'s list. In this case, cow (g)'s list (i.e. the interval ([g, E_g])) must either contain cow (h) (i.e. (E_g \ge h)) or, if it does not (i.e. (E_g = h-1)), then it must include all cows assigned as Guernsey (which, under a suitable assignment, are exactly the cows in positions (1) to (h-1)). Meanwhile, cow (h)’s list must include all Holstein cows. In order for this to be possible, all cows before position (h) must be assigned Guernsey and all cows from (h) to (E_h) Holstein.

2. If (h < g): By symmetry, when the earlier cow (cow (h)) is chosen as the Holstein leader and the later cow (cow (g)) as the Guernsey leader, the list of cow (h) must either contain cow (g) (i.e. (E_h \ge g)) or be exactly (g-1) (i.e. (E_h = g-1)), while cow (g)’s list will then cover all Guernsey cows (forcing all cows with indices less than (g) to be Holstein).

A careful analysis shows that in both cases (when (i < j)), an unordered pair ({i,j}) of cows can serve as the leader pair if and only if, when treating the cow with the smaller index as the leader writing the list, the following condition holds:

[ E_i \ge j \quad \text{or} \quad E_i = j - 1. ]

Your task is to compute the number of unordered pairs of cows ({i, j}) (with (i \neq j)) that could potentially be the leaders under some valid breed assignment.

It is guaranteed that there is at least one valid pair.

inputFormat

The first line contains a single integer (N) ((2 \le N \le 10^5)). The second line contains (N) integers (E_1, E_2, \ldots, E_N) (each satisfying (i \le E_i \le N)), where (E_i) is the last cow in cow (i)'s list.

outputFormat

Output a single integer representing the number of unordered pairs of cows that could be the leaders.

sample

2
1 2

1