Training Site
Sideways banner

Totem Pole

Input: Standard Input (stdin)
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.


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 a single integer, the number of people who will make carvings.


  • 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 data 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