Find Watson's integer Problem Statement:

Watson gives Sherlock an array \$A_1\$, \$A_2\$ ... \$A_N\$. 
He asks him to find an integer \$M\$ between \$P\$ and \$Q\$ (both inclusive), such that, \$\min \{|A_i-M|, 1 \le i \le N\}\$ is maximised. If there are multiple solutions, print the smallest one.

Input Format:

The first line contains \$N\$. The next line contains space separated N integers, and denote the array \$A\$. The third line contains two space separated integers denoting \$P\$ and \$Q\$.

Constraints:


\$1 \le N \le 10^2\$
\$1 \le A_i \le 10^9\$
\$1 \le P \le Q \le 10^9\$


My code:

#include &lt;bits/stdc++.h&gt;
int main()
{   int size,print,dist=INT_MIN,answer,start,end,diff;
    std::vector &lt;int&gt; arr;
    std::cin&gt;&gt;size;
    for(int i=0;i&lt;size;i++)
    {   int templ
        std::cin&gt;&gt;temp;
        arr.push_back(temp);
    }
    std::sort(arr.begin(),arr.end());
    std::cin&gt;&gt;start&gt;&gt;end;
    for(int i=start;i&lt;=end;i++)
    {   
        dist=INT_MAX;
        for(int j=0;j&lt;size;j++)
        {
            diff=fabs(i-arr[j]);
            if(diff&gt;dist)
                break;
            dist=std::min(dist,diff);

        }
        if(dist&gt;answer)
        {
            answer=dist;
            print=i;
        }
    }
    std::cout&lt;&lt;print;
    return 0;
}


My code is producing the output that I'm expecting, however it is failing with the hackerrank judge telling me that the time limit has been exceeded.

According to me its running time is O(n(p-q)).
Then it should clear all the test cases in less than 2s (assuming computer can compute 10^9 problems in a second, I remember reading somewhere that that's how most online judges work). At most my program will work on 10^11 problems (n*p-q= 10^2 *10^11).

Do my timing predictions make sense?

How can I improve my code, particularly the performance so that it is able to pass this judge?
General Advise
Online coding challenges may not be timed as far as how long it takes to write them. Take the time to write better code rather than rushing through it. Don't make assumptions about the size of data or the run time that is allowed, on line research may be incorrect about this, because times won't be posted. 

Big O Calculation
Does the Big O Calculation include the call to sort() if not, then that can be part of the timing problem.

Use Functions
The program is too complex and needs to be broken into functions. One function gets the array of numbers of input. Another function should do the calculation. The main() function should just control the program.

Declare Variables as Needed
There is a list of variables at the very beginning, this is more C like than C++. If the program is broken into functions this large list of variables at the top is not needed.

Meaningful Variable Names
The variable size is a good name, although the type might be size_t rather than int. The other variable names might be more meaningful if the were declared where they were needed.

Missing Includes
The code is missing some necessary include files:  

#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;algorithm&gt;


std::sort()
The call to sort is missing the third argument, which should be the comparison to use in the sort.