https://codeforces.com/contest/1077/problem/C

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's call an array good if there is an element in the array that equals to the sum of all other elements. For example, the array a=[1,3,3,7] is good because there is the element a4=7 which equals to the sum 1+3+3.

You are given an array a consisting of n integers. Your task is to print all indices j of this array such that after removing the j-th element from the array it will be good (let's call such indices nice).

For example, if a=[8,3,5,2], the nice indices are 1 and 4:

  • if you remove a1, the array will look like [3,5,2] and it is good;
  • if you remove a4, the array will look like [8,3,5] and it is good.

You have to consider all removals independently, i. e. remove the element, check if the resulting array is good, and return the element into the array.

Input

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

The second line of the input contains nn integers a1,a2,…,an (1≤ai≤106) — elements of the array a.

Output

In the first line print one integer k — the number of indices j of the array aa such that after removing the j-th element from the array it will be good (i.e. print the number of the nice indices).

In the second line print k distinct integers j1,j2,…,jk in any order — nice indices of the array a.

If there are no such indices in the array a, just print 0 in the first line and leave the second line empty or do not print it at all.

Examples

input

5
2 5 1 2 2

output

3
4 1 5

input

4
8 3 5 2

output

2
1 4

input

5
2 1 2 4 3

output

0

Note

In the first example you can remove any element with the value 2 so the array will look like [5,1,2,2]. The sum of this array is 10 and there is an element equals to the sum of remaining elements (5=1+2+2).

In the second example you can remove 8 so the array will look like [3,5,2]. The sum of this array is 10 and there is an element equals to the sum of remaining elements (5=3+2). You can also remove 2 so the array will look like [8,3,5]. The sum of this array is 16 and there is an element equals to the sum of remaining elements (8=3+5).

In the third example you cannot make the given array good by removing exactly one element.

C++版本一

 

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
typedef long long ll;
const int N=200000+100;
int t,n;
int b[N];
ll sum;
struct node{
    int x,id;
    bool operator <(const node& S)const{
        return x<S.x;

    }


}a[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].x);
        a[i].id=i;
        sum+=a[i].x;
    }
    sort(a+1,a+n+1);
    int ans=0;
    for(int i=1;i<n;i++){
        if(sum-a[i].x==2*a[n].x){
            b[++ans]=a[i].id;
        }

    }
    if(sum-a[n].x==2*a[n-1].x){
        b[++ans]=a[n].id;
    }

    cout << ans << endl;
    for(int i=1;i<=ans;i++){
        if(i!=ans)
            printf("%d ",b[i]);
        else
            printf("%d",b[i]);
    }
    cout << endl;
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

The first part: calculate the sum of the whole array: sum=∑i=1nai (be careful, it can be 2⋅1011!).

The second part: let's maintain an array cntcnt of size 106+1 where cnti will be equal to the number of elements in the given array equals to i.

The third part: iterate over the array, let the current position be i. Set sum:=sum−ai, make cntai:=cntai−1. If sumsum is even, sum2≤106 and cntsum2>0 then the index i is nice otherwise it doesn't. And after all make cntai:=cntai+1 and set sum:=sum+ai.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e6;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> cnt(MAX + 1);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		++cnt[a[i]];
	}
	long long sum = accumulate(a.begin(), a.end(), 0ll);
	
	vector<int> ans;
	for (int i = 0; i < n; ++i) {
		sum -= a[i];
		--cnt[a[i]];
		if (sum % 2 == 0 && sum / 2 <= MAX && cnt[sum / 2] > 0) {
			ans.push_back(i);
		}
		sum += a[i];
		++cnt[a[i]];
	}
	
	cout << ans.size() << endl;
	for (auto it : ans) cout << it + 1 << " ";
	cout << endl;
	
	return 0;
}