---{"category_name":"easy","problem_code":"CHEF7UP","problem_name":"Chef Up","problemComponents":{"constraints":"- $1 \\leq T \\leq 10$\n- $1 \\leq N \\leq 10^5$\n- $1 \\leq C \\leq 10^9$\n- $1 \\leq P_i \\leq 10^9$\n- All the coordinates are unique. That means $P_i \\ne C$ for all $1 \\le i \\le N$, and $P_i \\ne P_j$ for all $1 \\le i \\lt j \\le N$","constraintsState":true,"subtasks":"- 30 points : $1 \\leq R \\leq 10000$\n- 70 points : $1 \\leq R \\leq 10^9$\n","subtasksState":false,"inputFormat":"- The first line contains $T$ - the number of test cases. Then the test cases follow.\n- The first line of each test case contains a single integer $N$ - the number of officers.\n- The second line of each test case contains a single integer $C$ - the initial coordinate of Chef.\n- The third line of each test case contains $N$ integers $P_1, P_2, \\dots, P_N$ - the initial coordinates of the officers.\n\n","inputFormatState":true,"outputFormat":"For each test case, output on a single line two space-separated integers: the first integer is the maximum number of officers that can be eliminated by Chef, and the second integer is $1$ if Chef runs away or $-1$ if Chef will be caught.","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"2\n2\n2\n1 4\n1\n2\n1\n","output":"1 -1\n1 1\n","explanation":"- **Test case $1$**: Chef chooses to always move to the left (i.e. to the smaller coordinate); this forces the officer at coordinate $1$ to always move to the left, and eventually being cornered and eliminated. However, the officer at coordinate $4$ cannot be eliminated, and hence Chef will be caught at the end.\n- **Test case $2$**: Similarly, Chef chooses to always move to the left, and eventually eliminating the only officer, thus running away at the end.","isDeleted":false}}},"video_editorial_url":"https://youtu.be/g_aSGMtkM1k","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":1,"source_sizelimit":50000,"problem_author":"ashish99hanny","problem_tester":"","date_added":"22-10-2021","tags":{"0":"ad","1":"ashish99hanny","2":"cook134","3":"easy","4":"sorting"},"problem_difficulty_level":"Unavailable","best_tag":"Ad Hoc","editorial_url":"https://discuss.codechef.com/problems/CHEF7UP","time":{"view_start_date":1635100202,"submit_start_date":1635100202,"visible_start_date":1635100202,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=CHEF7UP","is_proctored":false,"visitedContests":{},"layout":"problem"}---### Read problem statements in [Mandarin](https://www.codechef.com/download/translated/COOK134/mandarin/CHEF7UP.pdf), [Bengali](https://www.codechef.com/download/translated/COOK134/bengali/CHEF7UP.pdf), and [Russian](https://www.codechef.com/download/translated/COOK134/russian/CHEF7UP.pdf) as well.Chef is a wanted criminal, and $N$ police officers are up for catching him. The officers want to catch Chef no matter the cost, and Chef also wants to eliminate as many officers as possible (preferably everyone) before getting caught (or before running away after eliminating everyone). Neither the officers nor Chef will run away before accomplishing their goals.Chef and the officers are on a one-dimensional grid with coordinates ranging from $-10^{10}$ to $10^{10}$. Chef is initially standing at coordinate $C$, and the $i$-th officer is initially at coordinate $P_i$. The officers and Chef then take turns to move, with the officer team moving first.During their turn, officers will have to move to an adjacent unoccupied cell one by one, in any order they want. Every officer will have to move. At every moment of time, no two officers can be in the same cell, and also no officer can be in the same cell as Chef. If the officer is unable to move to an adjacent unoccupied cell, he is eliminated (and the cell he was in becomes unoccupied). **Note that the officer team will try to move to eliminate as few officers as possible.** For example, with $P = [2, 3, 4]$ and $C = 6$, then the next positions of the officers can be $[1, 2, 3]$, $[1, 2, 5]$, $[1, 4, 5]$, or $[3, 4, 5]$. However, with $P = [2, 3, 4]$ and $C = 5$, the only possible set of the next positions of the officers is $[1, 2, 3]$.After the officer team's turn, Chef also moves to an adjacent unoccupied cell, or gets caught if he cannot find any adjacent unoccupied cell. The process then repeats until either Chef is caught, or all officers are eliminated and Chef runs away.You need to find out the maximum number of officers that can be eliminated by Chef, and if Chef can run away or not.As a reminder, two cells with coordinates $X$ and $Y$ are *adjacent* if and only if $|X - Y| = 1$.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>