Locked Away

Submit solution
Points: 1
Time limit: 1.0s
Memory limit: 256M
Author:
Tuga
Problem type
Allowed languages
C, C++, Java, Python

You are trying to break into AllUni Co. to steal the reference solutions to the contest problems, but Patrick and Patrick were one step ahead of you, implementing tough security by chaining locks together to secure the outside gates. Specifically, there is a chain of locks with n locks on it connected in a single line. Each lock is numbered 1 to n, with the lock labelled 1 being the leftmost lock.

However, luckily, you thought ahead and brought bolt cutters with you. Over time you will cut different locks off the chain to see what happens. You are interested in how many different contiguous segments of locks remain after all removals, so you can find a way to totally unlock the gate.

How many segments of connected locks will there be after all removals?

Input

The first line consists of two integers n and m (2 \leq n \leq 10^{12},1 \leq m \leq 10^{5},n > m) — the number of locks, and the number of removals.

The next line consists of m integers x_i (1 \leq x_i \leq n). Each integer in this line will be unique. x_i represents the number of the lock that will be removed at the ith time, labelled 1 to n.

Output

Output a single integer — the total amount of lock segments remaining after all m removals.

Example

Input 1
9 4
1 5 7 2
Output 1
3

Initially, we start with all 9 locks.

123456789

In each subsequent step of removing a lock, we will be left with the following segments:

 23456789 - removed lock 1
 234 6789 - removed lock 5
 234 6 89 - removed lock 7
  34 6 89 - removed lock 2

In the end, we are left with 3 distinct segments of locks, 34, 6, and 89.

Comments