There are NN people on a street (numbered 1 through N). For simplicity, we’ll view them as points on a line. For each valid ii, the position of the i-th person is Xi.

It turns out that exactly one of these people is infected with the virus COVID-19, but we do not know which one. The virus will spread from an infected person to a non-infected person whenever the distance between them is at most 2. If we wait long enough, a specific set of people (depending on the person that was infected initially) will become infected; let’s call the size of this set the final number of infected people.

Your task is to find the smallest and largest value of the final number of infected people, i.e. this number in the best and in the worst possible scenario.

### Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer N.
• The second line contains NN space-seperated integers X1,X2,…,XN.

### Output

For each test case, print a single line containing two space-separated integers ― the minimum and maximum possible final number of infected people.

### Constraints

• 1≤T≤2,0001≤T≤2,000
• 2≤N≤82≤N≤8
• 0≤Xi≤100≤Xi≤10 for each valid ii
• X1<X2<…<XNX1<X2<…<XN

Subtask #2 (90 points): original constraints

```3
2
3 6
3
1 3 5
5
1 2 5 6 7
```

```1 1
3 3
2 3
```

### Explanation

Example case 1: The distance between the two people is 3, so the virus cannot spread and at the end, there will always be only one infected person.

Example case 2: The distance between each two adjacent people is 2, so all of them will eventually get infected.

Example case 3:

• In one of the best possible scenarios, the person at the position 1 is infected initially and the virus will also infect the person at the position 2.
• In one of the worst possible scenarios, the person at the position 5 is infected initially and the virus will also infect the people at the positions 6 and 7.

## Coronavirus Spread – CodeChef Solution in JAVA

```import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner input = new Scanner(System.in);
int t = input.nextInt();
while(t-- >0){
int n = input.nextInt();
int min = n, max = 1,count = 1;
int Arr[] = new int[n];
for(int i = 0; i<n; i++){
Arr[i] = input.nextInt();
}
for(int i = 0 ,j =1; i<n && j <n; i++,j++ ){
if(Arr[j] - Arr[i] <= 2){
count++;
}else{
if(count >= max){
max = count;
}
if(count < min){
min = count;
}
count = 1;
}
}
if(count >= max){
max = count;
}
if(count < min){
min = count;
}
System.out.println(min + " " + max);
}
}
}
```

## Coronavirus Spread – CodeChef Solution in CPP

```#include <iostream>
#include<climits>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
int ar[n];
ar=0;
for(int i=1;i<n;i++){
ar[i]=a[i]-a[i-1];
}
int count=1,min=100,max=-1;
for(int i=1;i<n;i++){
if(ar[i]<=2){
count++;
}
else{
if(min>count){
min=count;
}
if(max<count){
max=count;
}
count=1;
}
}
if(min>count){
min=count;
}
if(max<count){
max=count;
}
cout<<min<<" "<<max<<"\n";
}
return 0;
}
```

## Coronavirus Spread -CodeChef Solution in Python

```from sys import stdin