Trong thế giới của Jujutsu Kaisen, Hắc Thiểm (Black Flash) là hiện tượng cực hiếm xảy ra khi chú lực được truyền vào đòn đánh gần như đồng thời với cú va chạm. Mỗi lần thực hiện thành công Hắc Thiểm sẽ đưa chú thuật sư đến gần hơn với trạng thái \(120\%\) tiềm năng, giúp sức mạnh bộc phát vượt xa giới hạn thông thường.

Sau trận chiến tại Shibuya, Itadori Yuji quyết định luyện tập Hắc Thiểm III. Trong quá trình luyện tập, Yuji liên tục thay đổi vùng chú lực để thử nghiệm các cách thi triển khác nhau.

Yuji có \(n\) đơn vị chú lực được đánh số từ \(1\) đến \(n\). Đơn vị chú lực thứ \(i\) có giá trị \(a_i\).

Gojo sẽ đưa ra \(q\) yêu cầu. Mỗi yêu cầu gồm hai số nguyên \(L, R\), nghĩa là Yuji chỉ được phép chọn một đoạn liên tiếp \([l, r]\) sao cho:
\(L \le l \le r \le R\)

Nếu chọn đoạn \([l, r]\), sức mạnh của Hắc Thiểm III được tính theo công thức:
\((r - l + 1) \cdot \min(a_l, a_{l+1}, \dots, a_r) + \max(a_l, a_{l+1}, \dots, a_r)\)

Trong đó:

• \(\min\) là lượng chú lực nhỏ nhất trong đoạn.
• \(\max\) là lượng chú lực lớn nhất trong đoạn.

Với mỗi yêu cầu, hãy tìm sức mạnh lớn nhất Yuji có thể tạo ra.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\).

Output

• In ra \(q\) dòng. Dòng thứ \(i\) là sức mạnh lớn nhất có thể đạt được đối với truy vấn thứ \(i\).

Constraints

• \(1 \le n, q \le 500\)
• \(1 \le a_i \le 10^9\)

Example

7 2
6 2 5 4 5 1 6
1 7
3 5

17
17