Binary Search#3451

Binary Search

1 second

64 megabytes

Very hard

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}, a_{1}, \dots, a_{n - 1}$ a_0, a_1, \ldots, a_{n-1}, $x$

$l = 0$ l = 0;

$r = n$ r = n;

while ( $l < r - 1$ l < r - 1) {

$m = (l + r) /2$ m = (l + r) / 2;

if ( $a_{m} \leq x$ a_m \leq x)

$l = m$ l = m;

else

$r = m$ r = m;

}

if ( $a_{l} == x$ 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 \leq n \leq 1000$ 1 \leq n \leq 1000).

Output

Output a single integer — the solution to the problem.

Examples

Example 1

Loading

a_{0}, a_{1}, \dots, a_{n - 1}

l = 0

r = n

l < r - 1

m = (l + r) /2

a_{m} \leq x

l = m

r = m

a_{l} == x

1 \leq n \leq 1000