Mảng và đoạn

Cho dãy số nguyên $a_1,a_2,\dots ,a_n$ và tập hợp $m$ đoạn. Đoạn thứ $j$ là $[l_j;r_j]$ với $1\le l_j\le r_j\le n$.

Bạn được chọn một tập con bất kỳ (có thể rỗng) của tập $m$ đoạn nói trên. Với mỗi đoạn được chọn, hãy giảm tất cả các phần tử trong đoạn đó của dãy $a$ đi $1$. Sau khi áp dụng tất cả các đoạn đã chọn, ta nhận được dãy mới $b$.

Hãy chọn tập con sao cho giá trị ${max}_{i=1}^n{b}_i-{min}_{i=1}^n{b}_i$ là lớn nhất có thể.

Nếu có nhiều phương án, in ra phương án bất kỳ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $m$ dòng tiếp theo, dòng thứ $j$ chứa hai số nguyên $l_j$ và $r_j$ mô tả đoạn thứ $j$.

Dữ liệu ra

• Dòng đầu tiên: một số nguyên $d$ — giá trị $max{b}_i-min{b}_i$ lớn nhất.
• Dòng thứ hai: một số nguyên $q$ — số đoạn được chọn.
• Dòng thứ ba: $q$ số nguyên phân biệt $c_1,c_2,\dots ,c_q$ (theo thứ tự bất kỳ) — chỉ số các đoạn được chọn.

Nếu $q=0$, dòng thứ ba có thể để trống.

Ràng buộc

• $1\le n\le 300$
• $0\le m\le 300$
• $-{10}^6\le a_i\le {10}^6$
• $1\le l_j\le r_j\le n$

Ví dụ