• محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • منبع: آزمون مقدماتی اول دوره ۲۶ المپیاد کامپیوتر

توابع f:N1,1f: \mathbb{N} \rightarrow {-1, 1} و g:NZg: \mathbb{N} \rightarrow \mathbb{Z} به صورت زیر تعریف می‌شوند:

f

g(n)=i=1nf(i)g(n)=\sum_{i=1}^{n}f(i)

در توضیحات بالا، منظور از N\mathbb{N} مجموعه‌ی اعداد طبیعی و منظور از Z\mathbb{Z} مجموعه‌ی اعداد صحیح است.

برنامه‌ای بنویسید که qq پرسمان به صورت (l,r)(l,r) دریافت کند و به ازای هر پرسمان تعداد نابجایی‌های دنباله‌ی g(l),g(l+1),,g(r)g(l), g(l+1), \ldots, g(r) را محاسبه کند. با توجه به این‌که پاسخ پرسمان‌ها می‌تواند بزرگ باشد، باقی‌مانده‌ی آن بر 109+710^9 + 7 را محاسبه کنید.

تعداد نابجایی‌های دنباله‌ی a1,a2,,ana_1, a_2, \ldots, a_n برابر است با تعداد جفت (i,j)(i,j) هایی که i<ji < j و ai>aja_i > a_j است.

ورودی

در سطر اول ورودی عدد طبیعی qq، تعداد پرسمان‌ها، آمده است.

در هر یک از qq سطر بعدی به ترتیب دو عدد طبیعی ll و rr آمده است.

1q50 0001\leq q\leq 50\ 000 1lr10181\leq l \leq r\leq 10^{18}

خروجی

خروجی شامل qq سطر است که در ii امین (1iq)(1\leq i\leq q) سطر از آن، پاسخ پرسمان ii ام آمده است.

زیرمسئله‌ها

زیرمسئله نمره محدودیت
۱ ۲۵ l,r1 000 000l,r \leq 1\ 000\ 000
۲ ۲۵ rl100,q10 000r - l \leq 100, q \leq 10\ 000
۳ ۵۰ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4
1 1
2 3
1 5
3 17
Plain text

خروجی نمونه ۱

0
0
2
25
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.