409066: GYM103428 L shake hands

There are $$$n$$$ lovely children standing in a row, numbered from $$$1$$$ to $$$n$$$ from left to right. Their positions are also numbered from $$$1$$$ to $$$n$$$ from left to right. Initially, no one has shaken hands with others. Their teacher is playing a game. In each turn, the teacher chooses two adjacent children and let them shake hands with each other. After shaking hands, the two children will swap their positions. After $$$m$$$ turns, the teacher asks you a question: can you choose some children as many as possible such that every pair of chosen children has shaken hands with each other?

The first line contains two integers $$$n, m$$$ ($$$2 \leq n \leq 2\cdot10^5,\ 1 \leq m \leq 2\cdot10^5$$$), denoting the number of children and operations.

In the next $$$m$$$ lines, each line contains an integer $$$x$$$ ($$$1 \leq x < n$$$), which means that in this turn, the children on the $$$x$$$-th position and $$$(x+1)$$$-th position shake hands with each other.

The only line contains an integer, denoting the maximum number of children that have shaken hands with each other.

6 12
1
3
5
1
2
3
5
4
3
2
4
4

4