/* Problem source: https://leetcode.com/problems/squares-of-a-sorted-array/
 */

#include <iostream>
#include <memory>
#include <vector>

template <typename T> inline T absolute(T num) {
  return num > -num ? num : -num;
}

template <typename T> inline T square(T num) { return num * num; }

template <typename T>
std::unique_ptr<std::vector<T>> solution(const std::vector<T> &sorted_input) {
  std::unique_ptr<std::vector<T>> sorted_output =
      std::make_unique<std::vector<T>>(sorted_input.size());
  unsigned long long p1 = 0, p2 = 1;
  while (p2 < sorted_input.size()) {
    if (absolute(sorted_input[p2]) <= absolute(sorted_input[p1]))
      p1 = p2++;
    else
      break;
  }

  //   std::cout << sorted_input[p1] << ", " << sorted_input[p2] << "\n";

  unsigned long long output_p = 0;
  while (p1 < p2 && p2 < sorted_input.size()) {
    if (absolute(sorted_input[p1]) < absolute(sorted_input[p2]))
      (*sorted_output)[output_p++] = (square(sorted_input[p1--]));
    else
      (*sorted_output)[output_p++] = square(sorted_input[p2++]);
  }
  while (p1 < p2)
    (*sorted_output)[output_p++] = square(sorted_input[p1--]);
  while (p2 < sorted_input.size())
    (*sorted_output)[output_p++] = square(sorted_input[p2++]);
  return sorted_output;
}

int main() {
  std::unique_ptr<std::vector<int>> result =
      solution(std::vector{-4, -1, 0, 3, 10});
  for (const int num : *result)
    std::cout << num << ", ";
  std::cout << std::endl;
}