nằm trên đoạn từ phần tử thứ
liđến phần tử thứ
ri".< /div>
Một dãy con của dãy a1 , ..., an< /sub> là một chuỗi có thể thu được bằng cách loại bỏ một số phần tử ai (thứ tự tương đối của các phần tử
còn lại
không thể thay đổi phần tử
). Vì vậy, ví dụ, dãy (2, 4) là dãy con của dãy (1, 2, 3, 4, 5) (bạn có thể xóa các phần tử 1, 3 và 5 ), và dãy ( 5, 1) thì không.
Đầu vào
Dòng đầu tiên chứa số nguyên
n (1 <= n <= 3000 ) là số phần tử của dãy. Dòng thứ hai chứa
n< /code> Các số được phân tách bằng dấu cách là các phần tử của dãy. Tất cả các phần tử không vượt quá 109 về giá trị tuyệt đối. Dòng thứ ba chứa một số nguyên duy nhất q< /code> (1 < ;= q <= 105) - số lượng yêu cầu. Các dòng q sau mô tả các truy vấn. Mô tả truy vấn thứ i - hai số li và rj (1 <= li <= ri <= n) , được phân tách bằng dấu cách.
Dữ liệu đầu ra
Xuất số q - câu trả lời cho truy vấn. Các số phải được xuất một số trên mỗi dòng theo cùng thứ tự như các truy vấn được mô tả trong đầu vào.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
6
3 3 -5 7 4 9
6
14
1 2
23
15
3 5
25 |
2
1
1
2
2
2 |