UTS Open '21 P3 - Latin Class

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

The school year has just started, and Edward has found out why Allen isn't in class sometimes. This year, he finally has Latin class with Allen and wants to sit next to him. In the classroom, there are N students seated in a line, the i^\text{th} student from the left having height h_i. At the start of every day, Mr. Carswell will partition all N students into any number of contiguous non-empty groups. However, being the naughty student he is, Allen will only show up to class if the maximum height of each group forms a non-descending sequence.

Please help Edward find the number of partitions of students that satisfy the given condition modulo 10^9+7.


For this problem, you will NOT be required to pass the sample cases in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N \le 10^5

1 \le h_i \le 10^9

Subtask 1 [15%]

1 \le N \le 21

Subtask 2 [25%]

1 \le h_i \le 100

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains an integer N, the number of students.

The next line contains N integers h_i (1 \le i \le N), the heights of the students.

Output Specification

Output one integer, the number of partitions that satisfy the given condition modulo 10^9+7.

Sample Input 1

2 1 2

Sample Output 1


Explanation for Sample 1

The three valid partitions (each represented by a set of ranges) are: \{[1, 1], [2, 3]\}, \{[1, 2], [3, 3]\}, \{[1, 3]\}.

Note that the partition \{[1, 1], [2, 2], [3, 3]\} is invalid since the sequence formed by the maximum height in each group is not non-descending.

Sample Input 2

1 3 7 4 7

Sample Output 2



There are no comments at the moment.