Module: GWP (بزرگترین دنباله افزایشی)


Problem

4 /6


NVP در بخش (A, A')

Problem

به ما یک دنباله اعداد داده می شود a1، ...، an . برنامه ای بنویسید که به پرس و جوهایی مانند "پیدا کردن طول بزرگترین جدید زیر دنباله، همه عناصر
پاسخ دهد.
که در قسمتی از liام تا عنصر riام قرار دارند.< / div>
یک زیر دنباله از دنباله a1 , ...، an< /sub> دنباله ای است که با حذف چندین عنصر ai (ترتیب نسبی باقیمانده
) بدست می آید. عناصر
قابل تغییر نیستند). بنابراین، برای مثال، دنباله (2، 4) دنباله ای از دنباله (1، 2، 3، 4، 5) است (شما می توانید عناصر 1، 3 و nbsp; و 5 را حذف کنید)،  و دنباله ( 5، 1) نیست.< br />  
ورودی
خط اول شامل یک عدد صحیح n  (1 <= n <= 3000 ) تعداد عناصر موجود در دنباله است. خط دوم حاوی n< /code>  اعداد جدا شده با فاصله عناصر دنباله هستند. همه عناصر در مقدار مطلق از 109 تجاوز نمی کنند. خط سوم شامل یک عدد صحیح منفرد q< /code>  (1 < ;= q <= 105) - تعداد درخواست‌ها. q  خطوط زیر پرس و جوها را توصیف می کند. توضیحات i -مین پرس و جو - دو عدد li و rj   (1 <= li <= ri <= n) با فاصله جدا شده است.
 
داده‌های خروجی
خروجی اعداد q - پاسخ به سوالات. اعداد باید یک خروجی در هر خط به همان ترتیبی که عبارت‌های جستجو در ورودی توضیح داده شده است.
 
نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1 6
3 3 -5 7 4 9
6
14
1 2
23
15
3 5
25		 2
1
1
2
2
2

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!