最近感受到了Codeforce的思维难度，真心感觉是一些非常棒的思维及配合STL使用，在这里简单总结一下：

第一个例题：

Coffee Break

题目描述：

Recently Monocarp got a job. His working day lasts exactly mm minutes. During work, Monocarp wants to drink coffee at certain moments: there are nn minutes a1,a2,…,ana1,a2,…,an, when he is able and willing to take a coffee break (for the sake of simplicity let's consider that each coffee break lasts exactly one minute).

However, Monocarp's boss doesn't like when Monocarp takes his coffee breaks too often. So for the given coffee break that is going to be on minute aiai, Monocarp must choose the day in which he will drink coffee during the said minute, so that every day at least dd minutes pass between any two coffee breaks. Monocarp also wants to take these nn coffee breaks in a minimum possible number of workingdays (he doesn't count days when he is not at work, and he doesn't take coffee breaks on such days). Take into account that more than dd minutes pass between the end of any working day and the start of the following working day.

For each of the nn given minutes determine the day, during which Monocarp should take a coffee break in this minute. You have to minimize the number of days spent.

Input

The first line contains three integers nn, mm, dd (1≤n≤2⋅105,n≤m≤109,1≤d≤m)(1≤n≤2⋅105,n≤m≤109,1≤d≤m) — the number of coffee breaks Monocarp wants to have, the length of each working day, and the minimum number of minutes between any two consecutive coffee breaks.

The second line contains nn distinct integers a1,a2,…,ana1,a2,…,an (1≤ai≤m)(1≤ai≤m), where aiai is some minute when Monocarp wants to have a coffee break.

Output

In the first line, write the minimum number of days required to make a coffee break in each of the nngiven minutes.

In the second line, print nn space separated integers. The ii-th of integers should be the index of the day during which Monocarp should have a coffee break at minute aiai. Days are numbered from 11. If there are multiple optimal solutions, you may print any of them.

Examples

Input

4 5 3
3 5 1 2

Output

3
3 1 1 2

Input

10 10 1
10 5 7 4 6 3 2 1 9 8

Output

2
2 1 1 2 2 1 2 1 1 2

Note

In the first example, Monocarp can take two coffee breaks during the first day (during minutes 11 and 55, 33 minutes will pass between these breaks). One break during the second day (at minute 22), and one break during the third day (at minute 33).

In the second example, Monocarp can determine the day of the break as follows: if the minute when he wants to take a break is odd, then this break is on the first day, if it is even, then this break is on the second day.

题目大意：

一个人想要在n个专用的时间点喝咖啡，但是每次必须最少间隔m秒，问最少可以几天喝完。具体意思看一下第一个样例理解：想要在 3 5 1 2 喝咖啡&&m=3，那么如果在1喝咖啡，那么下一次喝咖啡的时间就需要在 4之后的时间点喝咖啡，也就是5，这就是第一天的规划，随后第二天在2 喝咖啡，第三天在3喝咖啡，所以最少3天。（这样应该懂了吧，那就假设你们懂了）

题目思路：

1.首先，因为这篇博客不是总结例题的，而是总结思想的，所以我按照思想来总结。

2.这里引入了一个STL容器，set，顾名思义 set也就是集合的意思，集合就需要满足互异性，即在这里面出现的数字各不相同，并且set里面插入的时候会自动排序，比如说插入5 再插入 1 那么首元素还是1，类似于优先队列。

2.在这里set的使用起到了关键作用：

按照我们普通的思路，我们每天都要从最靠前并且没有使用的时间点s开始喝咖啡（因为这样能保证分成的天数最少），然后我们去找下一个时间点要求就是 s>=s+m+1，然后我们把使用过的时间点标记一下，然后for循环继续，从第一个没有被标记的点开展第二天，然后找到第一个 s>=s+m+1并且没有被标记的时间点，以此类推。

②在这里我们就发现，这样速度极低而且巨容易出错，首先我们二分查找次数太多而且标记没标记我们都需要判断并且条件复杂，这个时候我们就需要考虑到，我们标记一个元素不就是使这个元素下一次不会被查找到吗？我们可不可以直接扔掉这个元素呢？当然是可以的。答案就是set，set里面自带二分查找并且set可以删除元素，而且里面是由平衡树实现，速度实现很稳定。所以我们这里就可以想到，我们每次找到一个符合要求的点的时候，我们就把他扔掉，当第二次寻找时这个元素就不在这个集合里了，我们很方便的就找到了。

3.我们又发现这个题的输出，有点意思，输出每一个时间点在哪一天喝，这怎么办呢？当你把一个元素放入set时，他是第几个出现的也就乱了，所以这时我们可以建立 set的结构体呀，也因此这里需要对结构体内部的小于号进行重载，使其按照 val从小到大排序，而不是按照id从小到大。我们这样就可以新建立一个数组，找到满足条件的数之后直接 mp[e.id]=cnt，cnt为当前第几天。这样这个题就完成了。

附一下代码，重载结构体的内容在注释：

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod=10007;

const int INF=0x3f3f3f3f;

const int maxn=1e6+5;

struct node{
    int id;
    ll num;
};
ll n,l,m;
set<node>s;
int mp[maxn];
bool operator<(node a,node b)//重新定义小于号
{
    return a.num<b.num;//使其按照 num 排序
}
int main()
{
    scanf("%lld%lld%lld",&n,&l,&m);
    for(int i=1;i<=n;i++)
    {
        node x;
        scanf("%lld",&x.num);
        x.id=i;
        s.insert(x);
    }
    node now;now.num=1;
    ll cnt=1;
    while(!s.empty())
    {
        auto e=s.lower_bound(now);//自带二分查找函数，找大于等于now的第一个数，并且重载小于号之后，第三个参数要穿结构体，意思是 查找的时候找满足这个结构体num的第一个结构体
        if(e==s.end())//如果找不到 ，那就应该换一天了
        {
            cnt++;//天数+1
            now.num=1;//重新找到第一个小的数
        }
        else
        {
            node now1=*e;//*e就是一个结构体，e其实返回的是一个迭代器
            mp[now1.id]=cnt;
            s.erase(*e);//这是删除操作
            now.num=now1.num+m+1;
        }
    }
    printf("%lld\n",cnt);
    for(int i=1;i<=n;i++)
        printf("%d ",mp[i]);
    return 0;
}

通过这一个题我们就可以发现：

1.STL里面的set其实用处是非常多的，关于第一点当我们发现一些 使用过的 元素可能会对当前的程序，产生干扰时我们可以直接把其放入set，S.erase。

2.如果发现题目，有重复数字多余，我们也可以把他放入set因为set可以去重，并且set可以统计该数出现的次数，例如k=s.count(m)。

3.对于要求 对不断删减的序列进行二分查找的题目 这个时候98%的可能性要用set，并且这个时候每次都取首元素不太好取，因为需要用到迭代器，所以我们可以采取这种思路，定义一个最小值，最小值比集合里的任何一个数要小，再对其进行二分查找大于等于这个数的第一个数，绝对是set的首元素，这个思想比较重要。

4.set的思想应用我也就能想到这么多，关于其他的set应用我们不知道了(但是百分百还有很多，兄弟们一起去发觉)

第二个例题：

Bacteria

题目描述：

Recently Monocarp has created his own mini-laboratory!

The laboratory contains nn bacteria. Monocarp knows that he can merge any two bacteria having equalsizes, and the resulting bacterium will have the size equal to the sum of sizes of merged bacteria. For example, if two bacteria having sizes equal to 77 merge, one bacterium with size 1414 is the result.

It becomes hard to watch for many bacteria, so Monocarp wants to merge all of them into one bacterium. It may not be possible to do this with the bacteria Monocarp has, so he can buy any number of bacteria of any possible integer sizes in a special store.

You have to determine the minimum number of bacteria Monocarp has to buy to merge them with the nnbacteria his laboratory contains into exactly one bacterium.

Input

The first line contains one integer nn (1≤n≤2⋅105)(1≤n≤2⋅105) — the number of bacteria Monocarp's laboratory contains.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤109)(1≤ai≤109), where aiai is the size of the ii-th bacterium in the laboratory.

Output

If it is impossible to merge the bacteria (possibly after buying some) into only one bacterium, print -1.

Otherwise print the minimum number of bacteria Monocarp has to buy to merge them with the nn bacteria his laboratory contains into exactly one bacterium.

Examples

Input

2
1 4

Output

Input

3
3 6 9

Output

-1

Input

7
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Output

Note

In the first example Monocarp should buy one bacterium having size 11 and one bacterium having size 22. Then Monocarp will have 44 bacteria having sizes [1,4,1,2][1,4,1,2]. Then two bacteria having sizes 11 can be merged into one having size 22. Then Monocarp will have 33 bacteria having sizes [2,4,2][2,4,2]. Then two bacteria having sizes 22 can be merged into one having size 44. Then Monocarp will have 22 bacteria having sizes [4,4][4,4], which can be merged into one having size 88.

In the second example no matter which bacteria Monocarp will buy, he cannot merge all his bacteria.

In the third example Monocarp needs to buy one bacterium having size 10000000001000000000.

题目大意：

给定一些细菌的大小，毎次两个相同的细菌都可以合并成为一个 2*size的细菌，问最后是否可以合并成一个细菌，如果可以输出最小步数，如果不可以输出-1

题目思路：

1.这个题就是在锻炼我们的思维，每次取最小的两个看看这两个能否合并就可以了。这里思路也就这样，我想说的是用优先队列！！

2.优先队列是一种比普通队列高级的数据结构，你把元素放进去之后，他会自动按照某一种顺序排序，首元素也会发生改变，这个地方用set是不可以的。因为不可以出现重复数字！而且两个题不能用一个STL（不然我写两篇就一模一样了），而且set每次取首元素要么用迭代器，要么用上面所说的二分查找确定第一个数，这两种其实对于这个题而言比较麻烦。

3.所以，有了优先队列之后我们可以这样做：

①：我们将优先队列的排序规则定义成从小到大排序，即每次我们取的都是这群数里的最小值。我们取出两个那么这两个有两种可能即要么相等，要么不相等。

②：如果相等，则这两个合并成一个就可以了，把2*size放进去。

③：如果不相等，那么只需要判断一下他俩的商是不是2的幂即可，因为如果一个序列到最后可以合并成一个数那么这个序列必须是以2为公比的等比数列(这个我也是后来才发现的)，所以如果是2的幂，说明接下来小的可以转换为大的，那么我们就只把小的扔了，并且从外面拿一个，让他变成2*size放进去。否则，直接输出-1即可，因为绝对不可以化为一个数.

所以代码也就实现了：

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod=10007;

const int INF=0x3f3f3f3f;

const int maxn=1e6+5;

ll n;
priority_queue<ll,vector<ll>,greater<ll>>q;//创建一个 小元素 在上的 优先队列
bool judge(ll x)
{
    if((x&(x-1))==0) return true;//判断一个数是不是2的幂
    return false;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        ll x;
        scanf("%lld",&x);
        q.push(x);
    }
    ll res=0;
    ll cnt=0;
    while(q.size()>=2)//只剩下一个数就可以了！
    {
        ll n1=q.top();q.pop();
        ll n2=q.top();q.pop();//取元素，扔掉元素
        if(n1==n2)
            q.push(n1*2);
        else if(n1<n2&&judge(n2/n1))
        {
            res++;
            q.push(n1*2);
            q.push(n2);
        }
        else
        {
            res+=2;
            q.push(n1*2);
            q.push(n2*2);//放入元素
        }
        if(judge(n2/n1)==false) return puts("-1"),0;
    }
        printf("%lld\n",res);
    return 0;
}

我们总结一下这个题：

1.首先，这个题我们用了优先队列，具体使用在代码中展出。

2.这个题有一个很好的思想，就是如果一堆数到最后可以合并为一个数他们必然是一个等比数列！

3.判断一个数是不是2的幂不需要麻烦的用while循环直接 n&(n-1)==0即可判断

写完两个，最后一个例题我来说一个反常思维

Three Parts of the Array

题目描述：

You are given an array d1,d2,…,dnd1,d2,…,dn consisting of nn integer numbers.

Your task is to split this array into three parts (some of which may be empty) in such a way that each element of the array belongs to exactly one of the three parts, and each of the parts forms a consecutive contiguous subsegment (possibly, empty) of the original array.

Let the sum of elements of the first part be sum1sum1, the sum of elements of the second part be sum2sum2 and the sum of elements of the third part be sum3sum3. Among all possible ways to split the array you have to choose a way such that sum1=sum3sum1=sum3 and sum1sum1 is maximum possible.

More formally, if the first part of the array contains aa elements, the second part of the array contains bbelements and the third part contains cc elements, then:

sum1=∑1≤i≤adi,sum1=∑1≤i≤adi,

sum2=∑a+1≤i≤a+bdi,sum2=∑a+1≤i≤a+bdi,

sum3=∑a+b+1≤i≤a+b+cdi.sum3=∑a+b+1≤i≤a+b+cdi.

The sum of an empty array is 00.

Your task is to find a way to split the array such that sum1=sum3sum1=sum3 and sum1sum1 is maximum possible.

Input

The first line of the input contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of elements in the array dd.

The second line of the input contains nn integers d1,d2,…,dnd1,d2,…,dn (1≤di≤1091≤di≤109) — the elements of the array dd.

Output

Print a single integer — the maximum possible value of sum1sum1, considering that the condition sum1=sum3sum1=sum3 must be met.

Obviously, at least one valid way to split the array exists (use a=c=0a=c=0 and b=nb=n).

Examples

Input

5
1 3 1 1 4

Output

Input

5
1 3 2 1 4

Output

Input

3
4 1 2

Output

Note

In the first example there is only one possible splitting which maximizes sum1sum1: [1,3,1],[ ],[1,4][1,3,1],[ ],[1,4].

In the second example the only way to have sum1=4sum1=4 is: [1,3],[2,1],[4][1,3],[2,1],[4].

In the third example there is only one way to split the array: [ ],[4,1,2],[ ][ ],[4,1,2],[ ].

题目大意：给你一序列数，你需要把这些数分成三段，第一段与第三段的和必须相等，问这个和最大是多少，每段可以一个数字也不取，也就是说每一组数肯定有一组解是0.

题目思路：

1.为什么要引入这个题，是因为今天在做这个题的时候，发现了一个思想，叫做后缀和。

2.我们都习惯引用前缀和来计算一些数，然后对于这个题而言，因为区间连续，而且又是判断第一段与第三段，所以我们完全可以用一个前缀和与一个后缀和记录。

3.这时候在用二分优化一下查找，即我们枚举每一个前缀和，看是否能找到一个后缀和与他相等(用STL二分优化一下就可以了)，找到之后我们需要判断一下这个可不可以也就是说后几项加前几项不能超过n。处理一下就可以了，最后需要注意一个细节：可以为0，我们就是数组一个值为0就可以了。

代码呀：

#define MAX(x,y) ((x)>(y)?(x) : (y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod=10007;

const int INF=0x3f3f3f3f;

const int maxn=1e6+5;

ll n,a,b;
ll num[maxn];
ll f[maxn];
struct node{
    int id;
    ll val;
}g[maxn];
bool operator<(node a,node b)//还是重载机构体，与第一个set一样
{
    return a.val<b.val;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lld",&num[i]);
    ll qsum=0,hsum=0;
    for(int i=1;i<=n;i++)
    {
        qsum+=num[i];
        hsum+=num[n-i+1];
        f[i]=qsum;g[i].val=hsum;
        g[i].id=i;
    }
    g[n+1].id=0;g[n+1].val=0;
    f[0]=0;
    node no;
    sort(g+1,g+2+n);
    ll maxl=-INF;
    for(int i=0;i<=n;i++)
    {
        no.val=f[i];
        int e=lower_bound(g+1,g+2+n,no)-g;
        if(e==n+2) continue;
        else if((g[e].id+i)<=n&&g[e].val==f[i])
                maxl=max(maxl,g[e].val);
    }
    printf("%lld\n",maxl);
    return 0;
}

这个题没什么好总结的，只是觉得后缀和思想比较罕见把他记录下来

总结：

1.我们通过这三个题目可以看出，每一个题目都不同程度上使用了STL，所以说STL对于我们新手编程来说是比较重要的。

2.而且，STL如何运用即与题目关联起来是下一步要进行的训练，不能只有一个思维而写不出代码(现在我就是这种情况，嘤嘤嘤～)

3.还是那句话，一起加油兄弟，人一我百，人十我万！

CF&&gym&&STL应用及思维题目简单整理

Coffee Break

Bacteria

Three Parts of the Array