Totem Pole
Output: Standard Output (stdout)
Memory limit: 32 megabytes
Time limit: 1.0 seconds
A group of N people (1 \le N \le 100{,}000) are standing in a line to make carvings on a totem pole. The totem pole has T positions (1 \le T \le 100{,}000) where carvings can be made, at heights 1, 2, ..., T.
The i-th person has height H_i (1 \le H_i \le 100{,}000), and can only make a carving at heights up to H_i.
Each person in turn will make a carving at the highest position they can at which a carving hasn't been made yet. There may be no such position, in which case the person won't make a carving and will be sad.
Your task is to determine the number of people who will make carvings.
Input
The first line will contain two space-separated integers, N and T. The second line will contain N space-separated integers, the heights of the people in the order they will make the carvings.
Output
Output a single integer, the number of people who will make carvings.
Subtasks
- Subtask 1 (40%): 1 \le N, T, H_i \le 1{,}000
- Subtask 2 (10%): 1 \le N, T \le 1{,}000
- Subtask 3 (50%): 1 \le N, T \le 100{,}000
Sample Explanation
The first three people make carvings at heights 2, 3, and 1. The fourth person can't make a carving because all the positions they can reach already have carvings. The last person makes a carving at height 4.
-
Sample Input 1
5 4 2 3 2 3 6
Sample Output 1
4