#include <iostream>
#include <iterator>

// With C++20 concepts
#include <concepts>

template<typename F, typename T>
concept unary_operation = std::invocable<F, T>
    && std::same_as<T, std::invoke_result_t<F, T>>;

template<
    std::input_iterator I,
    std::bidirectional_iterator D,
    unary_operation<std::iter_value_t<I>> NegateOp
    >

    requires std::same_as<std::iter_value_t<I>, std::iter_value_t<D>>
        && std::regular<std::iter_value_t<I>> 

// Without C++20 concepts 
/* 
template<typename I, typename D, typename NegateOp>
*/

D free_reduce(I first, I last, D out, NegateOp negate)
{
  if (first == last) return out;

  D out_start = out;
  *out = *first;
  ++out;
  ++first;

  while (first != last)
  {
    if (out != out_start && negate(*first) == *(out - 1))
    {
        --out;
    }
    else
    {
       *out = *first;
       ++out;
    }
    ++first;
  }

  return out;
}


template<
    std::input_iterator I,
    std::bidirectional_iterator D,
    unary_operation<std::iter_value_t<I>> NegateOp
    >
    requires std::same_as<std::iter_value_t<I>, std::iter_value_t<D>>

D word_negate(I first, I last, D d_first, NegateOp negate)
{
  D d_last = std::transform(first, last, d_first, negate);
  std::reverse(d_first, d_last);
  return d_last;
}


template<
    std::bidirectional_iterator I,
    unary_operation<std::iter_value_t<I>> NegateOp
    >

void word_negate_inplace(I first, I last, NegateOp negate)
{
   word_negate(first, last, first, negate);
}

template<std::bidirectional_iterator I>
void word_negate_inplace(I first, I last)
{
   word_negate(first, last, first, std::negate<std::iter_value_t<I>>());
}


template<typename I>
void print_word(I start, I end)
{
    while (start != end)
    {
        std::cout << (*start) << " ";
        ++start;
    }
    std::cout << std::endl;
}

int main(int argc, const char* argv[])
{
  int word[] = { 3, -2, 1, -1, 2, 7, -1, 1, 4 };
  constexpr size_t n = sizeof(word) / sizeof(int);


  {
    int out[n];
    int* end_out = free_reduce(word, word + n, out, std::negate());
    print_word(out, end_out);
  }

  {
    int out[n];
    int* end_out = word_negate(word, word + n, out, std::negate());
    print_word(out, end_out);
  }

  {
     word_negate_inplace(word, word + n);
     print_word(word, word + n);
  }

  return 0;
}