Last minute enhancements
Contest: Good Bye 2020
Difficulty rating: 800
Tags: dp, greedy

Athenaeus has just finished creating his latest musical composition and will present it tomorrow to the people of Athens. Unfortunately, the melody is rather dull and highly likely won't be met with a warm reception.

His song consists of $$$n$$$ notes, which we will treat as positive integers. The diversity of a song is the number of different notes it contains. As a patron of music, Euterpe watches over composers and guides them throughout the process of creating new melodies. She decided to help Athenaeus by changing his song to make it more diverse.

Being a minor goddess, she cannot arbitrarily change the song. Instead, for each of the $$$n$$$ notes in the song, she can either leave it as it is or increase it by $$$1$$$.

Given the song as a sequence of integers describing the notes, find out the maximal, achievable diversity.

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases. Then $$$t$$$ test cases follow, each one is described in two lines.

In the first line of each test case there is a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) denoting the length of the song. The next line contains a sequence of $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ $$$(1 \leq x_1 \leq x_2 \leq \ldots \leq x_n \leq 2 \cdot n)$$$, describing the song.

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, you should output a single line containing precisely one integer, the maximal diversity of the song, i.e. the maximal possible number of different elements in the final sequence.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Euterpe can increase the second, fifth and sixth element to obtain the sequence $$$1, \underline{3}, 2, 2, \underline{6}, \underline{7}$$$, which has $$$5$$$ different elements (increased elements are underlined).

In the second test case, Euterpe can increase the first element to obtain the sequence $$$\underline{5}, 4$$$, which has $$$2$$$ different elements.

In the third test case, Euterpe can increase the second, fifth and sixth element to obtain the sequence $$$1, \underline{2}, 3, 4, \underline{5}, \underline{6}$$$, which has $$$6$$$ different elements.

Example input:
5
6
1 2 2 2 5 6
2
4 4
6
1 1 3 4 4 5
1
1
6
1 1 1 2 2 2

Example output:
5
2
6
1
3

Editorial:
We describe two solutions.
The first focuses on maximal contiguous intervals of values. We notice that for each such interval $$$[l, r]$$$ it can either remain unchanged or get increased to $$$[l, r + 1]$$$ (other possibilities won't increase the number of different elements; thus, we don't need to consider them). From this observation, we conclude that the result is the number of different elements in the input increased by the number of intervals containing at least one duplicate.
The second is based on a simple, greedy approach, where we analyze the elements in nondecreasing order. While analyzing, we keep the set of elements for which we have already decided its value. When we want to add the next element, then we check if it is in the set. If it is, we increase it by $$$1$$$; otherwise, we keep it as it is.