Array and Segments (Easy version) CodeForces

The only difference between easy and hard versions is a number of elements in the array.

You are given an array aa consisting of nn integers. The value of the ii-th element of the array is aiai.

You are also given a set of mm segments. The jj-th segment is [lj;rj][lj;rj], where 1≤lj≤rj≤n1≤lj≤rj≤n.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a=[0,0,0,0,0]a=[0,0,0,0,0] and the given segments are [1;3][1;3] and [2;4][2;4] then you can choose both of them and the array will become b=[−1,−2,−2,−1,0]b=[−1,−2,−2,−1,0].

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array aaand obtain the array bb then the value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi will be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains two integers nn and mm (1≤n≤300,0≤m≤3001≤n≤300,0≤m≤300) — the length of the array aa and the number of segments, respectively.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (−106≤ai≤106−106≤ai≤106), where aiai is the value of the ii-th element of the array aa.

The next mm lines are contain two integers each. The jj-th of them contains two integers ljlj and rjrj (1≤lj≤rj≤n1≤lj≤rj≤n), where ljlj and rjrj are the ends of the jj-th segment.

Output

In the first line of the output print one integer dd — the maximum possible value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi if bb is the array obtained by applying some subset of the given segments to the array aa.

In the second line of the output print one integer qq (0≤q≤m0≤q≤m) — the number of segments you apply.

In the third line print qq distinct integers c1,c2,…,cqc1,c2,…,cq in any order (1≤ck≤m1≤ck≤m) — indices of segments you apply to the array aa in such a way that the value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi of the obtained array bb is maximum possible.

If there are multiple answers, you can print any.

Examples

Input

5 4
2 -2 3 1 2
1 3
4 5
2 5
1 3

Output

6
2
1 4 

Input

5 4
2 -2 3 1 4
3 5
3 4
2 4
2 5

Output

7
2
2 3 

Input

1 0
1000000

Output

0
0

Note

In the first example the obtained array bb will be [0,−4,1,1,2][0,−4,1,1,2] so the answer is 66.

In the second example the obtained array bb will be [2,−3,1,−1,4][2,−3,1,−1,4] so the answer is 77.

In the third example you cannot do anything so the answer is 00.

题意：

一个包含N个元素的数组，和M个区间

你可以选择这M个区间中的某些个使用，每使用一个 区间可以使区间对应数组中的元素值减去1，每一个区间最多使用一次。

让求出使用某些个（可以是0个）区间后，数组的最大值减去最小值最大。并输出选择了哪些区间。

思路：

由于数据量亲民，我们只需要枚举1~n的每一个位置，以那个位置不我们数组渴望的不变值，即选择的区间不应该包括他，

然后把不包括他的区间都使用，然后暴力的求最大差值，中间维护下最值信息和对应选择的点即可。

数据量比较小，任意暴力出答案就可以了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
int q;
int a[maxn];
struct node
{
    int l,r;
}qj[maxn];
int ji[305];
int main()
{
    gg(n);
    gg(q);
    int d=-1*inf;
    int did;
    std::vector<int> v;
    int jr=inf;
    repd(i,1,n)
    {
        gg(a[i]);
        if(a[i]>d)
        {
            v.clear();
            did=i;
            d=a[i];
            v.push_back(i);
        }else if(a[i]==d)
        {
            v.push_back(i);
        }
        jr=min(jr,a[i]);
    }
    repd(i,1,q)
    {
        gg(qj[i].l);
        gg(qj[i].r);
    }
    int ans=d-jr;
    std::vector<int> aa;
    std::vector<int> fu;
    for(int i=1;i<=n;i++)
    {
        int id=i;
        MS0(ji);
        fu.clear();
        repd(j,1,q)
        {
            if(qj[j].l<=id&&qj[j].r>=id)
            {
                continue;
            }else
            {
                repd(p,qj[j].l,qj[j].r)
                {
                    ji[p]--;
                }
                fu.push_back(j);
            }
        }
        int jjr=inf;
        int da=-1*inf;
        repd(i,1,n)
        {
            da=max(da,a[i]+ji[i]);
            if((a[i]+ji[i])<jjr)
            {
                jjr=(a[i]+ji[i]);
            }
        }
        if(da-jjr>ans)
        {
            ans=da-jjr;
            aa=fu;
        }
    }
    printf("%d
",ans );
    printf("%d
",sz(aa));
    for(auto w:aa)
    {
        printf("%d ", w);
    }
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '
');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}