Binary Search
Binary search is an algorithm used to locate a specific element within a sorted array. Below is the pseudocode for a binary search algorithm, where "/" indicates integer division:
input: a[0..n-1], x
l=0;
r=n;
while ( l < r-1 ) {
m=(l+r)/2;
if(a[m]<=x)
l=m;
else
r=m;
}
if(a[l]==x)
return true;
else
return false;
Occasionally, binary search may successfully find an element in the array even if the array is not sorted. You are given a number n. Your task is to determine the number of pairs <a, x>, where a is an array of length n containing integers from 1 to n, and x is an integer from 1 to n, such that the above procedure returns "true" when executed with the array a and the integer x as inputs.
Input
The input consists of a single integer n (1 ≤ n ≤ 1000).
Output
Output a single integer — the solution to the problem.