1083 : ลงทุนซื้อหุ้น (stock)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)

        เรื่องเริ่มต้นเมื่อวันหนึ่งคุณได้ข่าวมา ว่า มีอัญมณีอันล้ำค่ายิ่งกว่าที่เคยมีใครพบเจอถูกซ่อนอยู่... ได้เวลาปลุกความเป็นนักล่าสมบัติของคุณแล้ว! แต่กลับมีอุปสรรคสำคัญมาขวางคุณซะได้... เพราะการสำรวจทางโบราณคดีใดๆนั้นต้องใช้งบประมาณอยู่มาก คุณจึงตัดสินใจที่จะเอาเงินที่คุณมีไปลงทุนในตลาดหุ้น

        เนื่องจากราคาหุ้นของบริษัทต่างๆ ขึ้นอยู่กับข่าวสารที่จะมาชี้ชะตาอนาคตของบริษัท และบางครั้งคุณก็ไม่ได้รู้ข่าวพวกนี้พร้อมกับคนอื่น ทำให้คุณอาจเสียเปรียบคนอื่นได้ แต่ด้วยสมองอันปราดเปรื่องของคุณ คุณได้สร้างเครื่องทำนายราคาหุ้นล่วงหน้ามา

สมมติว่า เครื่องให้ข้อมูลราคาหุ้นในวันต่างๆ เป็นดังนี้
         วันที่ 1 ราคา 10
         วันที่ 2 ราคา 20
         วันที่ 3 ราคา 15
         วันที่ 4 ราคา 12
         วันที่ 5 ราคา 21
         วันที่ 6 ราคา 30

        ในช่วงวันที่ 1-6 คุณจะสามารถทำกำไรได้ 28 บาท โดยซื้อวันที่ 1 ขายวันที่ 2 และ ซื้อวันที่ 4 ขายวันที่ 6 (เริ่มต้นคุณมีเงินไม่จำกัด)

         คุณมีข้อมูลราคาหุ้นอยู่ n วัน และคุณต้องการตอบคำถาม q คำถาม โดยแต่ละคำถามจะถาม
ว่า ในช่วงการลงทุนตั้งแต่วันที่ aj ถึงวันที่ bj ที่กำหนดให้ คุณจะสามารถทำการซื้อและขายหุ้นในช่วง
เฉพาะในช่วงวันดังกล่าว (หรือก็คือช่วง [aj, bj]) ให้ได้กำไรสูงสุดเท่าไร

        เนื่องจากคุณไม่ต้องการให้เครื่องทำนายราคาหุ้นของคุณเป็นที่จับตามองของนักลงทุนคนอื่น ๆ
คุณจึงถือหุ้นในมือ ณ ขณะใด ๆ ไม่เกินหนึ่งหน่วยเท่านั้น (การถือหุ้นต้องถือเป็นจำนวนเต็มหน่วย
เท่านั้น)

เนื่องจากคุณไม่ต้องการให้เครื่องทำนายราคาหุ้นของคุณเป็นที่จับตามองของนักลงทุนคนอื่น ๆ
คุณจึงถือหุ้นในมือ ณ ขณะใด ๆ ไม่เกินหนึ่งหน่วยเท่านั้น (การถือหุ้นต้องถือเป็นจำนวนเต็มหน่วย
เท่านั้น)

งานของคุณ
         จงเขียนโปรแกรมรับราคาหุ้นที่เครื่องของคุณทำนายออกมา และช่วงการลงทุนที่คุณต้องการทราบกำไร จากนั้นให้แสดงผลกำไรสูงสุดที่คุณสามารถทำได้สำหรับแต่ละช่วงที่กำหนด

ข้อมูลนำเข้า
        บรรทัดที่ 1 มีจำนวนเต็มบวก n (1<=n<=1,000,000) แทนจำนวนวันที่คุณมีข้อมูลราคาหุ้น
        บรรทัดที่ 2 มีจำนวนเต็มบวกอยู่ n ตัว ตัวที่ i แทนราคาของหุ้นในวันที่ i โดยราคาหุ้นในแต่ละวันจะมีค่าไม่เกิน 7,000
        บรรทัดที่ 3 มีจำนวนเต็มบวก q (1<=q<=1,000,000) แทนจำนวนช่วงการลงทุนที่คุณต้องการทราบกำไร
        บรรทัดที่ 4…q+3 มีจำนวนเต็มบวก 2 ตัว a b (1<=a, b<=n) แทนวันเริ่มต้นและวันสิ้นสุดของแต่ละช่วงการลงทุน

ข้อมูลส่งออก
        มี q บรรทัด บรรทัดที่ i มีจำนวนเต็มบวกหนึ่งตัว แทนกำไรที่มากที่สุดที่คุณสามารถทำได้ในช่วงที่ i

โจทย์โดย: วรภัทร บุญญฤทธิพงษ์
ที่มา: TOI.CPP:03-2009


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
6
10 20 15 12 21 30
3
1 6
2 4
3 5
28
0
9

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 19 ผู้เยี่ยมชมและ 5 สมาชิก (2 บอท)