2030 : พิสัยพิเศษ (range)
Problem type : Batch
Time limit : 0.4 second(s)
Memory limit : 64 megabyte(s)

    เรามีลำดับของจำนวนเต็ม N จำนวน แทนด้วย a₁,a₂,a₃,…,a_N เราต้องการทราบจำนวนของลำดับย่อย a_i,a_i+1,a_i+2,…,a_j (ซึ่ง i≤j) ที่มีพิสัยของลำดับย่อยเป็นจำนวนเต็มที่อยู่ในช่วง [p,q] ว่ามีกี่ลำดับย่อย
    นิยาม พิสัยของลำดับจำนวนหนึ่ง ๆ คือผลต่างของค่าสูงสุดและต่ำสุดของลำดับดังกล่าว  ดังนั้นพิสัยของลำดับย่อย a_i,a_i+1,a_i+2,…,a_j ก็คือ max(a_i,a_i+1,a_i+2,…,a_j) - min(a_i,a_i+1,a_i+2,…,a_j)
    สมมติลำดับของจำนวนเต็ม 7 ตัวมี 1, 7, 4, 3, 9, 6, 8 พบว่าจะมีลำดับย่อยทั้งหมด 13 ลำดับย่อยที่มีค่าพิสัยอยู่ในช่วงตั้งแต่ 4 ถึง 6 ได้แก่ 1-7-4-3,  1-7-4,  1-7,  7-4-3-9-6-8,  7-4-3-9-6,  7-4-3-9,  7-4-3,  4-3-9-6-8,  4-3-9-6,  4-3-9,  3-9-6-8, 3-9-6 และ 3-9 

งานของคุณ

    คุณจะต้องรับลำดับของจำนวนเต็ม แล้วหาว่ามีลำดับย่อยกี่ลำดับที่มีค่าพิสัยมากกว่าหรือเท่ากับ p และน้อยกว่าหรือเท่ากับ q

ข้อมูลนำเข้า

    บรรทัดแรกมีจำนวนเต็มสามจำนวนคือ N,p,q บอกความยาวของลำดับจำนวนและช่วงพิสัยที่สนใจตามลำดับ (1≤N≤1,000,000 และ 0≤p≤q≤10,000,000)
    อีก N บรรทัดถัดมา จะมีข้อมูลของจำนวนในลำดับ โดยข้อมูลในบรรทัดที่ i+1 จะมีจำนวนเต็ม a_i ซึ่งหมายถึงจำนวนที่ i ของลำดับ (0≤a_i≤10,000,000)

ข้อมูลส่งออก

    มีจำนวนเต็มจำนวนเดียวบอกจำนวนของลำดับย่อยที่มีพิสัยอยู่ในช่วง [p,q]

การให้คะแนน

    ชุดข้อมูลทดสอบมูลค่าไม่เกิน 40 คะแนน มีค่า N≤1,000    ชุดข้อมูลทดสอบมูลค่าไม่เกิน 70 คะแนน มีค่า N≤100,000 และ ในทุกชุดข้อมูลทดสอบมีค่า N≤1,000,000

 

โจทย์โดย: อาภาพงศ์ จันทร์ทอง
ที่มา: TOI.C:05-2009

 

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
7 4 6 1 7 4 3 9 6 8	13

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