- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
«مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا...
حتما داستان هنرنمایی لیته و فیته بر روی صحنه را به یاد دارید. اکنون، مدّت زیادی از آن هنرنمایی می‌گذرد و لیته و فیته حسابی هنرمندان ماهری شده‌اند.
مسریکس همراه با باقر و بی‌قر، دو نفر از دوستانش، برای تماشای هنرنمایی جدید لیته و فیته به سالن تئاتر رفته است. در همان لحظه فکری هوشمندانه به ذهن مسریکس می‌رسد و به باقر و بی‌قر می‌گوید هر کدام دو صندلی خالی از دو ردیف مختلف سالن تئاتر انتخاب کنند. به عبارت دیگر، باقر باید یک ردیف را انتخاب کند و سپس از آن ردیف دو صندلی خالی انتخاب کند. سپس بی‌قر باید یک ردیف دیگر را انتخاب کرده و دو صندلی خالی از آن ردیف انتخاب کند.
در سالن تئاتر $n$ صندلی خالی وجود دارد. فرض کنید باقر صندلی‌های شماره‌ی $t_1$ و $t_2$ را از سطر $r_1$ انتخاب کند و بی‌قر صندلی‌های شماره‌ی $s_1$ و $s_2$ را از سطر $r_2$ انتخاب کند.
این ۴ صندلی را باقرپسند می‌گوییم اگر ۲ شرط زیر به ازای آن‌ها برقرار باشد.
- $r_1 < r_2$
- $t_1 < s_1 < t_2 < s_2$
و آن‌ها را بی‌قرپسند می‌گوییم اگر ۲ شرط زیر به ازای آن‌ها برقرار باشد.
- $r_1 < r_2$
- $s_1 < t_1 < s_2 < t_2$
مسریکس می‌خواهد «تعداد حالاتی که ۴ صندلی انتخاب شده بی‌قرپسند باشند» منهای «تعداد حالاتی که ۴ صندلی انتخاب شده باقرپسند باشند» را محاسبه کند تا بر اساس آن‌ها راهکاری برای بحران محیط زیست پیدا کند. لطفا باقی‌مانده‌ی این مقدار به $1\ 000\ 000\ 007$ را برای مسریکس محاسبه کنید.
برای راحتی فرض کنید سالن تئاتر متشکّل از $n$ ستون است و در هر ستون دقیقا یک صندلی خالی وجود دارد. شماره‌ی ردیف صندلی خالی‌ای که در ستون $i$ام قرار دارد برابر با $a_i$ است.
ورودی
در سطر اوّل ورودی عدد $n$ آمده است.
در سطر دوم $n$ عدد آمده است که نشان‌دهنده‌ی آرایه‌ی $a$ هستند.
$$1 \le n \le 100\ 000$$ $$1 \leq a_i\leq 10^9$$
خروجی
در تنها سطر خروجی، باقی مانده‌ی «تعداد حالاتی که ۴ صندلی انتخاب شده بی‌قرپسند باشند» منهای «تعداد حالاتی که ۴ صندلی انتخاب شده باقرپسند باشند» به $1\ 000\ 000\ 007$ را چاپ کنید.
مثال
ورودی نمونه ۱
6
2 2 1 2 1 2
خروجی نمونه ۱
1
ورودی نمونه ۲
9
2 2 1 2 1 3 2 2 2
خروجی نمونه ۲
1000000006
توضیح: در این مثال، اختلاف تعداد حالاتِ گفته شده برابر $-1$ است که باقی‌مانده‌اش به $1\ 000\ 000\ 007$ برابر با مقدار چاپ شده است.
ارسال پاسخ برای این سؤال