A Subarray Problem

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

Given a permutation p of the integers 1 to N, find the number of subarrays that satisfy the following property:

  • If the maximum element it contains is M, then it contains all of the integers 1 to M

Input Specification

The first line will contain N.

The following line will contain N integers p_i for 1 \leq i \leq N

Output Specification

Output the number of subarrays with the described property.

Constraints

1 \leq N \leq 10^6

1 \leq p_i \leq N

The given p_i are guaranteed to form a permutation of the integers 1 to N.

Sample Input 1

1
1

Sample Output 1

1

Sample Input 2

2
2 1

Sample Output 2

2

Sample Input 3

3
1 3 2

Sample Output 3

2

Comments

There are no comments at the moment.