이진 탐색

이진 탐색은 정렬된 배열에서 주어진 원소를 찾는 알고리즘입니다. 다음은 이진 탐색의 의사 코드입니다 (<</>>는 정수 나눗셈을 뜻합니다):

입력: 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;

배열이 정렬되어 있지 않아도 이진 탐색이 배열에서 어떤 원소를 찾아내는 경우가 있습니다. 정수 $n$이 주어집니다. 길이가 $n$이고 원소가 1부터 $n$까지의 정수인 배열 $a$와, 1부터 $n$까지의 정수 $x$로 이루어진 쌍 $\langle a, x\rangle$ 중에서, 배열 $a$와 수 $x$를 인자로 위 절차를 실행했을 때 "true"를 반환하는 쌍의 개수를 구하시오.

입력 파일은 정수 $n$ ($1 \le n \le 1000$) 하나를 포함합니다.

문제의 답인 정수 하나를 출력하세요.