An equilibrium index of a sequence is an index into the sequence such that the sum of elements at lower indices is equal to the sum of elements at higher indices.



For example, in a sequence   



A


{\displaystyle A}

:

   




A

0


=
−
7


{\displaystyle A_{0}=-7}


   




A

1


=
1


{\displaystyle A_{1}=1}


   




A

2


=
5


{\displaystyle A_{2}=5}


   




A

3


=
2


{\displaystyle A_{3}=2}


   




A

4


=
−
4


{\displaystyle A_{4}=-4}


   




A

5


=
3


{\displaystyle A_{5}=3}


   




A

6


=
0


{\displaystyle A_{6}=0}


3   is an equilibrium index, because:

   




A

0


+

A

1


+

A

2


=

A

4


+

A

5


+

A

6




{\displaystyle A_{0}+A_{1}+A_{2}=A_{4}+A_{5}+A_{6}}


6   is also an equilibrium index, because:

   




A

0


+

A

1


+

A

2


+

A

3


+

A

4


+

A

5


=
0


{\displaystyle A_{0}+A_{1}+A_{2}+A_{3}+A_{4}+A_{5}=0}


(sum of zero elements is zero)

7   is not an equilibrium index, because it is not a valid index of sequence 



A


{\displaystyle A}

.



Task;
Write a function that, given a sequence, returns its equilibrium indices (if any).

Assume that the sequence may be very long.




#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
 
template <typename T>
std::vector<size_t> equilibrium(T first, T last)
{
    typedef typename std::iterator_traits<T>::value_type value_t;
 
    value_t left  = 0;
    value_t right = std::accumulate(first, last, value_t(0));
    std::vector<size_t> result;
 
    for (size_t index = 0; first != last; ++first, ++index)
    {
        right -= *first;
        if (left == right)
        {
            result.push_back(index);
        }
        left += *first;
    }
    return result;
}
 
template <typename T>
void print(const T& value)
{
    std::cout << value << "\n";
}
 
int main() 
{
    const int data[] = { -7, 1, 5, 2, -4, 3, 0 };
 
    std::vector<size_t> indices(equilibrium(data, data + 7));
 
    std::for_each(indices.begin(), indices.end(), print<size_t>);
}