补题报告个人赛2020.4.12

There are quite a lot of ways to have fun with inflatable balloons. For example, you can fill them with water and see what happens.

Grigory and Andrew have the same opinion. So, once upon a time, they went to the shop and bought $n$

They want to divide the balloons among themselves. In addition, there are several conditions to hold:

Do not rip the packets (both Grigory and Andrew should get unbroken packets);
Distribute all packets (every packet should be given to someone);
Give both Grigory and Andrew at least one packet;
To provide more fun, the total number of balloons in Grigory's packets should not be equal to the total number of balloons in Andrew's packets.

Help them to divide the balloons or determine that it's impossible under these conditions.

Input

The first line of input contains a single integer $n$

The second line contains $n$

Output

If it's impossible to divide the balloons satisfying the conditions above, print $- 1$

Otherwise, print an integer $k$

If there are multiple ways to divide balloons, output any of them.

Examples

Input

3
1 2 1

Output

2
1 2

Input

2
5 5

Output

-1

Input

1
10

Output

-1
题解：就是把n个气球带分开保证每人起码都有气球，问是否能使他们两个的气球数量不同，如果不行输出1
排个序把最少气球的分给一个人其他的分给另外一个人就可以了。
注意输出的是序号

#include<iostream>
#include <algorithm>
using namespace std;
struct ballon{
    int x;
    int num;
};
bool cmp(ballon p,ballon q){
        return p.x<q.x;
}
int main(){
    int n,sum1,sum2;
    ballon a[1001];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].x;
        a[i].num=i+1;
    }
    if(n<2){
        cout<<-1<<endl;
    }
    else{
        sort(a,a+n,cmp);
        sum1=a[0].x;
        sum2=a[1].x;
        if(n==2&&sum1==sum2){
            cout<<-1<<endl;
            return 0;
        }
        for(int i=2;i<n;i++){
            sum2+=a[i].x;
        }
        cout<<1<<endl;
        cout<<a[0].num<<endl;
    }
    return 0;
}

B - Cutting

There are a lot of things which could be cut — trees, paper, "the rope". In this problem you are going to cut a sequence of integers.

There is a sequence of integers, which contains the equal number of even and odd numbers. Given a limited budget, you need to make maximum possible number of cuts such that each resulting segment will have the same number of odd and even integers.

Cuts separate a sequence to continuous (contiguous) segments. You may think about each cut as a break between two adjacent elements in a sequence. So after cutting each element belongs to exactly one segment. Say, $[4, 1, 2, 3, 4, 5, 4, 4, 5, 5]$

The cost of the cut between $x$

Input

First line of the input contains an integer $n$

Second line contains $n$

Output

Print the maximum possible number of cuts which can be made while spending no more than $B$

Examples

Input

6 4
1 2 5 10 15 20

Output

Input

4 10
1 3 2 4

Output

Input

6 100
1 2 3 4 5 6

Output

题解：就是记录奇数的个数和偶数的个数如果相同就把他们和后面一个数分开记录分开用到的钱，然后排个序贪心，从最小钱的数开始计算，只
要小于等于b就接着算。（一开始以为只能从左到右进行计算）

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
    int n,b,sum=0,ans=0,k=0;
    int flagj=0;
    int flago=0;
    int a[1001];
    int cost[1001];
    cin>>n>>b;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        if(a[i]%2==0){
            flago++;
        }
        else{
            flagj++;
        }
        if(flagj==flago){
            if(i+1==n){
                break;
            }
            else{
                sum=abs(a[i+1]-a[i]);
                cost[k]=sum;
                k++;
            }
        }
    }
    sort(cost,cost+k);
    for(int i=0;i<k;i++){
        if(b>=cost[i]){
            ans++;
            b=b-cost[i];
        }
        else{
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

D - Sonya and Hotels

Sonya decided that having her own hotel business is the best way of earning money because she can profit and rest wherever she wants.

The country where Sonya lives is an endless line. There is a city in each integer coordinate on this line. She has $n$

Sonya understands that her business needs to be expanded by opening new hotels, so she decides to build one more. She wants to make the minimum distance from this hotel to all others to be equal to $d$

Because Sonya is lounging in a jacuzzi in one of her hotels, she is asking you to find the number of cities where she can build a new hotel so that the minimum distance from the original $n$

Input

The first line contains two integers $n$

The second line contains $n$

Output

Print the number of cities where Sonya can build a new hotel so that the minimum distance from this hotel to all others is equal to $d$

Examples

Input

4 3
-3 2 9 16

Output

Input

5 2
4 8 11 18 19

Output

5
题解：给定每个酒店的坐标再给每个酒店之间相隔的最小距离，问还可以再加入多少个酒店。如果前一个酒店+d坐标和后一个酒店-d坐标相等
那么他们之间只能有一个酒店sum++，如果后一个酒店-前一个酒店的距离大于2d表面他们之间有2个酒店sum+=2。最后的酒店和最前的酒店另外判断就好

#include<iostream>
using namespace std;
int main(){
    int n,d,sum=0;
    int a[1001];
    cin>>n>>d;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=2;i<=n;i++){
        if(a[i]-d==a[i-1]+d){
            sum++;
        }
        if(a[i]-d>a[i-1]+d){
            sum+=2;
        }
    }
    cout<<sum+2;
}

E - Sonya and Exhibition

Sonya decided to organize an exhibition of flowers. Since the girl likes only roses and lilies, she decided that only these two kinds of flowers should be in this exhibition.

There are $n$

She knows that exactly $m$

Sonya wants her exhibition to be liked by a lot of people. That is why she wants to put the flowers in such way that the sum of beauties of all segments would be maximum possible.

Input

The first line contains two integers $n$

Each of the next $m$

Output

Print the string of $n$

If there are multiple answers, print any.

Examples

Input

Output

Input

Output

110010
题解：题目意思就是从i-j玫瑰花数量*百合花数量要最大，其实就一个规律只要交叉放就好了。

#include<iostream>
using namespace std;
int main(){
    int n,m;
    int a[1001],b[1001];
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
    }
    for(int i=1;i<=n;i++){
        if(i%2){
            cout<<1; 
        }
        else{
            cout<<0;
        }
    }
    cout<<endl;
    return 0;
}

F - Sonya and Robots

Since Sonya is interested in robotics too, she decided to construct robots that will read and recognize numbers.

Sonya has drawn $n$

Sonya does not want robots to break, so she will give such numbers that robots will stop before they meet. That is, the girl wants them to stop at different positions so that the first robot is to the left of the second one.

For example, if the numbers $[1, 5, 4, 1, 3]$

Sonya understands that it does not make sense to give a number that is not written in the row because a robot will not find this number and will meet the other robot.

Sonya is now interested in finding the number of different pairs that she can give to robots so that they will not meet. In other words, she wants to know the number of pairs ( $p$

Unfortunately, Sonya is busy fixing robots that broke after a failed launch. That is why she is asking you to find the number of pairs that she can give to robots so that they will not meet.

Input

The first line contains a single integer $n$

The second line contains $n$

Output

Print one number — the number of possible pairs that Sonya can give to robots so that they will not meet.

Examples

Input

5
1 5 4 1 3

Output

Input

7
1 2 1 1 1 3 2

Output

题解：给出 n 个数字，让从这个序列中选一对数 (a,b)，使得从左边数第一个 a 出现的位置大于从右边数第一个 b 出现的位置，求符合要求的对数

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1000001
#define MOD 1e9+7
#define E 1e-6
#define LL long long
using namespace std;
int a[N],bucket[N],vis[N];
int main()
{
    int n;
    scanf("%d",&n);
 
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        if(bucket[a[i]]++==0)//这个数字有几个 
            cnt++;//几种数字 
    }
    LL ans=0;
    for(int i=0;i<n;i++)
    {
        if(--bucket[a[i]]==0)
            cnt--;//如果这个数字没有了种类-1 
        if(!vis[a[i]])
        {    
            ans+=cnt; 
            vis[a[i]]=1;
        }
    }
    printf("%lld
",ans);
    return 0;
}