Module: GWP (Surutan Meningkat Terbesar)


Problem

4 /6


NVP pada segmen (A, A')

Problem

Kami diberi urutan nombor a1, ..., an . Tulis program yang bertindak balas kepada pertanyaan seperti "cari panjang ketat meningkatkan urutan yang terbesar, semua elemen
yang terdapat pada segmen daripada lith ke rielemen".< / div>
Jujukan daripada jujukan a1 , ..., an< /sub> ialah jujukan yang boleh diperoleh dengan mengalih keluar beberapa elemen ai (urutan relatif baki
elemen tidak boleh diubah). Jadi, sebagai contoh, jujukan (2, 4) ialah jujukan kepada jujukan (1, 2, 3, 4, 5) (anda boleh memadamkan unsur 1, 3   dan 5 ),  dan jujukan ( 5, 1) tidak.< br />  
Input
Baris pertama mengandungi integer n  (1 <= n <= 3000 ) ialah bilangan elemen dalam jujukan. Baris kedua mengandungi n< /code>  Nombor yang dipisahkan oleh ruang ialah unsur-unsur jujukan. Semua elemen tidak melebihi 109 dalam nilai mutlak. Baris ketiga mengandungi integer tunggal q< /code>  (1 < ;= q <= 105) - bilangan permintaan. q  baris berikut menerangkan pertanyaan. Penerangan tentang pertanyaan i -th - dua nombor li dan rj   (1 <= li <= ri <= n) , dipisahkan dengan ruang.
 
data Output
Output q nombor - jawapan kepada pertanyaan. Nombor hendaklah dikeluarkan satu baris dalam susunan yang sama seperti pertanyaan yang diterangkan dalam input.
 
Contoh

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!

# Input Output
1 6
3 3 -5 7 4 9
6
14
1 2
23
15
3 5
25		 2
1
1
2
2
2