이진 삼진 탐색 놀이 2

서준이는 오늘도 아빠와 함께 알고리즘 놀이를 한다. 서준이는 이진 탐색, 아빠는 삼진 탐색을 한다.

서로 다른 정수가 오름차순으로 정렬된 크기 $N$의 배열 $A$가 있다. 이진 탐색과 삼진 탐색으로 배열 $A$의 $i$번째 원소 $A_i$를 찾을 때, $A_i$를 찾기 전에 참조하는 배열 $A$의 원소 개수를 각각 $B_i$, $T_i$라고 하자. 서준이는 아빠로부터 $[i, j]$ 구간에 대한 $T$의 합에서 $B$의 합을 뺀 값을 출력하는 $Q$개의 질의를 받았다. $N$과 $Q$가 커서 괴로워하는 서준이를 도와주자.

크기 $N$인 배열에서 이진 탐색 알고리즘의 의사 코드는 다음과 같다.

binary_search(A[0..N-1], value, left, right) {
    mid = (left + right) / 2
    if (A[mid] == value)
        return mid
    else if (value < A[mid])
        return binary_search(A, value, left, mid - 1)
    else
        return binary_search(A, value, mid + 1, right)
}

크기 $N$인 배열에서 삼진 탐색 알고리즘의 의사 코드는 다음과 같다.

ternary_search(A[0..N-1], value, left, right) {
    left_third = left + (right - left) / 3
    right_third = right - (right - left) / 3
    if (A[left_third] == value) 
        return left_third
    else if (A[right_third] == value)
        return right_third
    else if (value < A[left_third])
        return ternary_search(A, value, left, left_third - 1)
    else if (value < A[right_third])
        return ternary_search(A, value, left_third + 1, right_third - 1)
    else
        return ternary_search(A, value, right_third + 1, right)
}

첫째 줄에 질의의 수 $Q(1 \le Q \le 500{,}000)$가 주어진다. 둘째 줄부터 $Q+1$번째 줄까지 질의의 정보 $N$ $S$ $E$가 주어진다. $N$은 배열 $A$의 원소 개수, $S$는 구간의 시작, $E$는 구간의 끝을 나타낸다.

첫 번째 질의부터 $Q$번째 질의까지 각 질의의 결과를 한 줄씩 출력한다.

• $1 \le N \le 5{,}000$
• $1 \le Q \le 500{,}000$
• $0 \le S \le E < N$