Given an array *v* of *n* numbers, where *n*=2^{k}, *k*>0 be a natural number, find the minimum and maximum element in *v*. There are no assumptions regarding the orders of the elements of *v*. A basic iterative approach would require 2(*n*-1) comparisons (*n*-1 comparisons to find the minimum and *n*-1 comparisons to find the maximum). However, your program **MUST** perform at most 3/2*n*-1 comparisons.

**Difficulty**: Easy.

### Input

There are two lines.

- The first line contains an integer
`n`

representing the length of`v`

- The second line consists of
`n`

numbers separated by space which represent the array`v`

.

At the end of each line, there are no extra spaces, and there is a \`n`

.

### Output

One line containing 2 numbers separated by space, which are the smallest and biggest elements in `v`

respectively.

### Example

Input:

`8`

`3 1 6 8 5 9 -2 7`

Output:

`-2`

`9`

### Hint

You can use a divide-and-conquer paradigm.

### Solution: C++

```
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
using namespace std;
int* find_min_max(int v[], int l, int r){
//find min and max in v[l,..,r-1]
int* min_max = new int[2];
if(r-l==1){ //if array has exactly 1 element -> min==max
min_max[0]=min_max[1]=v[l];
return min_max;
}
int s=(r-l)/2+l;
int* min_max_l=find_min_max(v, l, s); //find min_max in v[l,...,s-1]
int* min_max_r=find_min_max(v, s, r); //find min_max in v[s,...,r-1]
if(min_max_l[0]<min_max_r[0])
min_max[0]=min_max_l[0];
else
min_max[0]=min_max_r[0];
if(min_max_l[1]>min_max_r[1])
min_max[1]=min_max_l[1];
else
min_max[1]=min_max_r[1];
//min_max[0]==min(v[l,...,r-1]), min_max[1]==max(v[l,..,r-1])
return min_max;
}
int main(){
int n;
cin>>n; //length of the array
int v[n];
for(int i=0; i<n; i++)
cin>>v[i];
int *min_max = find_min_max(v, 0, n);
cout<<min_max[0]<<" "<<min_max[1]<<endl;
}
```