NINJA5  K NUMBERS
Problem statement:
You are given N numbers from 1 to N. Now, your task is to choose some numbers from the N numbers (including 1 & N) such that no two numbers are consecutive. As this is easy, you are given an extra task. You have to definitely choose K numbers which are given. Find the maximum number of numbers that you can choose in such a way.
Input:
The first line has an integer T, the number of test cases.
Then for each test case, the first line has two integers N and K.
Then the next line has K numbers which you should definitely chooose.
Output:
For each test case, print the maximum number of numbers that you can choose.
Constraints:
1 <= T <= 100
2 <= N <= 2 x 10 ^ 6
1 <= K <= N / 2
1 <= X[1...K] <= N
Sample input:
1
8 2
6 2
Sample output:
4
hide comments
anirudnits:
20181117 09:11:59
if any of the two given K numbers are already consecutive, then just print 0. Worked for me! 

nadstratosfer:
20180424 19:47:04
Can't pass in raw Python and O(klogk) slower than O(n) in PyPy. Poorly set problem. 

singlasahil221:
20170723 07:15:50
Very easy.AC in one go.O(n) solution exists. 

bsiddhartha:
20170620 07:06:23
no sorting :) just take char array of size max n.and O(n+t)solution 

roshanarya905:
20170618 12:28:34
qsort giving TLE why? @himanshuz1 Last edit: 20170618 12:33:46 

manjur1996:
20161028 13:28:50
need to tighten the time.... O(n) easily excepted 

himanshu kumar:
20160721 13:39:17
O(n+k) solution passes it easily... while sorting gives tle 

hodobox:
20160704 07:51:27
My code does not account for the already selected numbers being consecutive 

Piyush Kumar:
20160619 20:58:36
If the question can be done in O(n), I think the constraints can be a little tighter. My O(nlogn) passed comfortably! 

Admin Deepak Baghel:
20160609 12:54:58
i think there is bug in test cases may be any two of the given K numbers are consecutive already. Last edit: 20160609 12:59:49 
Added by:  mombassa 
Date:  20160217 
Time limit:  0.200s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 