NINJA5 - K NUMBERS

no tags 

You are given N numbers from 1 to N. Now, your task is to choose some numbers from the N numbers (including 1 and 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 choose.

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

Output:
4


hide comments
Piyush Kumar: 2016-06-19 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: 2016-06-09 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: 2016-06-09 12:59:49
Sushovan Sen: 2016-05-30 13:30:35

Are values of k sorted?

sri: 2016-02-28 10:17:53

O(n) accepting

Last edit: 2016-02-28 10:18:12
lalit_nit: 2016-02-25 06:23:53

smone provide any tricky tst case please.....
EDIT:...LOL just new line causes many WA... Easy

Last edit: 2016-02-25 09:27:44
Siddharth Singh: 2016-02-21 11:20:38

Easy Problem if u get the logic
AC in 1 Go
And It Also Brings Up My 200th AC <3

Prateek Agarwal: 2016-02-21 08:00:24

time limit for python is strict. Python 2.7.10 code gives TLE.same code in C++ 5.1 passes in 0.07s

Sankaranarayanan G: 2016-02-21 07:14:08

Thanks @Ankit

Ankit: 2016-02-20 21:16:23

Lovey Problem. :) @mombassa


Added by:mombassa
Date:2016-02-17
Time limit:0.200s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY