Nam có ước mơ được tham gia các kỳ thi ICPC và Olympic Tin Học Sinh Viên vào năm 2025 tại trường đại học HUTECH.

Tuy nhiên, để được tham gia, Nam phải tham gia vào CLB phải thực hiện một bài tập thử thách cuối cùng:

Cho một dãy gồm N số nguyên A_1, A_2 … A_n. CLB Olympic Tin Học yêu cầu Nam thực hiện Q phép biến đổi trên dãy này theo thứ tự cho trước. Mỗi phép biến đổi được mô tả bởi hai số nguyên L và R. Phép biến đổi phải thay thế tất cả các giá trị từ vị trí L đến R ở trong dãy bằng giá trị cao nhất hoặc thấp nhất trong các số nằm trong đoạn từ L đến R.

Sau khi thực hiện phép biến đổi này, số lượng phần tử trong dãy sẽ giảm đi R-L phần tử. CLB Olympic Tin Học muốn biết có bao nhiêu dãy khác nhau mà Nam có thể tạo ra được sau khi hoàn thành Q phép biến đổi.

Tuy nhiên, vì kết quả có thể rất lớn, Nam chỉ cần đưa ra phần dư của số lượng dãy khác nhau (ban đầu và đã sinh ra) chia cho 10^9 +7.

• Dòng đầu tiên chứa số nguyên N là độ dài mảng
• Dòng thứ hai chứa N số nguyên A_1, A_2 … A_n cách nhau bằng khoảng trắng
• Dòng thứ ba chứa số nguyên Q là số phép biến đổi.
• Q dòng tiếp theo, mỗi dòng chứa 2 số L và R (1 ≤ L < R ≤ độ dài dãy hiện tại ) cách nhau bằng khoảng trắng.

Điều kiện:

• 1≤ N, Q ≤10^5
• 1 ≤ A_i ≤ 10^9 với 1 ≤ i ≤ N
• 1 ≤ L < R ≤ độ dài dãy hiện tại

Số nguyên dương là kết quả của số lượng dãy khác nhau sau khi hoàn thành Q thao tác sau khi chia modulo (10^9 +7)

Giải thích ví dụ 1: Thực hiện các thao tác: Dãy ban đầu: [1,2 ,2, 3, 4]

Thao tác 1: (1, 4)

• Đoạn từ vị trí 1 đến 4 của dãy là: 1 ,2, 2, 3
• Sau thao tác này, dãy có thể trở thành hai dãy:
  • [1, 4] (tất cả thay bằng giá trị nhỏ nhất).
  • [3, 4] (tất cả thay bằng giá trị lớn nhất).

Thao tác 2: (1, 2) Áp dụng thao tác trên cả hai dãy kết quả từ thao tác 1:

• Dãy [1, 4]:

  • Đoạn từ vị trí 1 đến 2 là: 1, 4.
  • Sau thao tác này, dãy trở thành 2 dãy
    • [1] (tất cả thay bằng GTNN)
    • hoặc [4] (tất cả thay bằng GTLN)

• Dãy [3, 4]:

  • Đoạn từ vị trí 1 đến 2 là: 3, 4.
  • Sau thao tác này dãy trở thành 2 dãy [3] hoặc [4].

Kết quả: Sau 2 thao tác, có 3 dãy khác nhau được tạo ra (dãy 4 trùng). Số lượng dãy khác nhau khi modulo là 3.