E. Хамгийн урт өсч буй дэд жагсаалт

хугацааны хязгаарлалт 1.5 секунд

санах ойн хязгаарлалт 128 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Энэ бодлогоны санах ой хэвийнээс бага гэдгийг санаарай.

Дундаа зайтай эерэг бүхэл тооны жагсаалт байна.

Энэ зайг нөхөх зориулалттай тооны цуглуулга бидэнд байгаа. Цуглуулгын тоо болгон нэг л удаа ашиглагдах боломжтой.

Таны даалгавар бол энэ жагсаалтын зайг нөхөн хамгийн урт өсч буй дэд жагсаалтыг олох юм.

Оролт

Эхний мөрөнд жагсаалтын урт болох $n$ ($1 ≤ n ≤ 10^{5}$) бүхэл тоо өгөгдөнө.

2 дахь мөрөнд жагсаалтын тоонууд болох $n$ ширхэг зайгаар тусгаарлагдсан бүхэл тоо өгөгдөнө. Зайг $-1$-ээр тэмдэглэнэ. Жагсаалтны зайг илэрхийлж байгаа тооноос бусад бүх тоонууд нь эерэг бүхэл тоо бөгөөд $10^{9}$-ыг хэтрэхгүй. Жагсаалтанд байгаа нийт зайн $0 ≤ k ≤ 1000$-ээс хэтрэхгүй тоо хэмжээтэй.

3 дахь мөрөнд зайг нөхөх зориулалттай тооны цуглуулгын тоо хэмжээ болох $m$ ($k ≤ m ≤ 10^{5}$) бүхэл тоо өгөгдөнө.

4 дэхь мөрөнд зайг нөхөх зориулалттай тоонууд болох $m$ ширхэг бүхэл тоо өгөгдөнө. Тоо болгон эерэг бүхэл тоо бөгөөд $10^{9}$-ыг хэтрэхгүй. Зарим тоонууд хоорондоо тэнцүү байх боломжтой.

Гаралт

Хамгийн урт өсч буй дэд жагсаалт болох $n$ ширхэг зайгаар тусгаарлагдсан тоог хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
3
1 2 3
1
10
Гаралт
1 2 3 
Оролт
3
1 -1 3
3
1 2 3
Гаралт
1 2 3 
Оролт
2
-1 2
2
2 4
Гаралт
2 2 
Оролт
3
-1 -1 -1
5
1 1 1 1 2
Гаралт
1 1 2 
Оролт
4
-1 -1 -1 2
4
1 1 2 2
Гаралт
1 2 1 2 

Тэмдэглэл

Эхний жишээнд нэг ч зай байхгүй учраас анхны жагсаалтыг өөрчлөх шаардлагагүй.

2 дахь жишээнд $3$ урттай өсч буй дэд жагсаалтыг үүсгэх ганцхан арга байна.

3 дахь жишээнд хариу $4 2$-г тооцно. Учир нь зөвхөн өсч буй дараалалтай дэд жагсаалтыг тооцно.

5 дахь жишээнд хариу $1 1 1 2$-г тооцохгүй. Учир нь $1$ тоо зөвхөн 2 удаа нөхөх зорилгоор ашиглах боломжтой.

Сэтгэгдлүүдийг ачааллаж байна...