While playing yet another strategy game, Mans has recruited n [Swedish heroes](https://www.youtube.com/watch?v=5sGOwFVUU0I), whose powers which can be represented as an array a.

Unfortunately, not all of those mighty heroes were created as capable as he wanted, so that he decided to do something about it. In order to accomplish his goal, he can pick two consecutive heroes, with powers a_i and a_{i+1}, remove them and insert a hero with power -(a_i+a_{i+1}) back in the same position. 

For example if the array contains the elements [5, 6, 7, 8], he can pick 6 and 7 and get [5, -(6+7), 8] = [5, -13, 8].

After he will perform this operation n-1 times, Mans will end up having only one hero. He wants his power to be as big as possible. What's the largest possible power he can achieve?

Input

The first line contains a single integer n (1 ≤ n ≤ 200000).

The second line contains n integers a_1, a_2, …, a_n (-10^9 ≤ a_i ≤ 10^9) — powers of the heroes.

Output

Print the largest possible power he can achieve after n-1 operations.

Examples

Input


4
5 6 7 8


Output


26


Input


5
4 -5 9 -2 1


Output


15

Note

Suitable list of operations for the first sample:

[5, 6, 7, 8] → [-11, 7, 8] → [-11, -15] → [26]
#include <bits/stdc++.h>
using namespace std;
template <typename T>
T qpow(T val, long long pow) {
  T ans = 1, base = val;
  while (pow) {
    if (pow & 1) ans *= base;
    base *= base;
    pow >>= 1;
  }
  return ans;
}
template <typename T, int NDIMS>
struct tensor_view {
  static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

 protected:
  std::array<int, NDIMS> shape;
  std::array<int, NDIMS> strides;
  T* data;
  tensor_view(std::array<int, NDIMS> shape_, std::array<int, NDIMS> strides_,
              T* data_)
      : shape(shape_), strides(strides_), data(data_) {}

 public:
  tensor_view() : shape{0}, strides{0}, data(nullptr) {}

 protected:
  int flatten_index(std::array<int, NDIMS> idx) const {
    int res = 0;
    for (int i = 0; i < NDIMS; i++) {
      res += idx[i] * strides[i];
    }
    return res;
  }
  int flatten_index_checked(std::array<int, NDIMS> idx) const {
    int res = 0;
    for (int i = 0; i < NDIMS; i++) {
      assert(0 <= idx[i] && idx[i] < shape[i]);
      res += idx[i] * strides[i];
    }
    return res;
  }

 public:
  T& operator[](std::array<int, NDIMS> idx) const {
    return data[flatten_index(idx)];
  }
  T& at(std::array<int, NDIMS> idx) const {
    return data[flatten_index_checked(idx)];
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type operator[](
      int idx) const {
    std::array<int, NDIMS - 1> nshape;
    std::copy(shape.begin() + 1, shape.end(), nshape.begin());
    std::array<int, NDIMS - 1> nstrides;
    std::copy(strides.begin() + 1, strides.end(), nstrides.begin());
    T* ndata = data + (strides[0] * idx);
    return tensor_view<T, NDIMS - 1>(nshape, nstrides, ndata);
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type at(
      int idx) const {
    assert(0 <= idx && idx < shape[0]);
    return operator[](idx);
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 == D), T&>::type operator*() const {
    return *data;
  }
  template <typename U, int D>
  friend struct tensor_view;
  template <typename U, int D>
  friend struct tensor;
};
template <typename T, int NDIMS>
struct tensor {
  static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

 protected:
  std::array<int, NDIMS> shape;
  std::array<int, NDIMS> strides;
  int len;
  T* data;

 public:
  tensor() : shape{0}, strides{0}, len(0), data(nullptr) {}
  explicit tensor(std::array<int, NDIMS> shape_, const T& t = T()) {
    shape = shape_;
    strides[NDIMS - 1] = 1;
    for (int i = NDIMS - 1; i > 0; i--) {
      strides[i - 1] = strides[i] * shape[i];
    }
    len = strides[0] * shape[0];
    data = new T[len];
    std::fill(data, data + len, t);
  }
  tensor(const tensor& o)
      : shape(o.shape), strides(o.strides), len(o.len), data(new T[len]) {
    for (int i = 0; i < len; i++) {
      data[i] = o.data[i];
    }
  }
  tensor& operator=(tensor&& o) noexcept {
    using std::swap;
    swap(shape, o.shape);
    swap(strides, o.strides);
    swap(len, o.len);
    swap(data, o.data);
    return *this;
  }
  tensor(tensor&& o) : tensor() { *this = std::move(o); }
  tensor& operator=(const tensor& o) { return *this = tensor(o); }
  ~tensor() { delete[] data; }
  using view_t = tensor_view<T, NDIMS>;
  view_t view() { return tensor_view<T, NDIMS>(shape, strides, data); }
  operator view_t() { return view(); }
  using const_view_t = tensor_view<const T, NDIMS>;
  const_view_t view() const {
    return tensor_view<const T, NDIMS>(shape, strides, data);
  }
  operator const_view_t() const { return view(); }
  T& operator[](std::array<int, NDIMS> idx) { return view()[idx]; }
  T& at(std::array<int, NDIMS> idx) { return view().at(idx); }
  const T& operator[](std::array<int, NDIMS> idx) const { return view()[idx]; }
  const T& at(std::array<int, NDIMS> idx) const { return view().at(idx); }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type operator[](
      int idx) {
    return view()[idx];
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<T, NDIMS - 1>>::type at(
      int idx) {
    return view().at(idx);
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<const T, NDIMS - 1>>::type
  operator[](int idx) const {
    return view()[idx];
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 < D), tensor_view<const T, NDIMS - 1>>::type at(
      int idx) const {
    return view().at(idx);
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 == D), T&>::type operator*() {
    return *view();
  }
  template <int D = NDIMS>
  typename std::enable_if<(0 == D), const T&>::type operator*() const {
    return *view();
  }
};
template <typename T>
void setmax(T& a, T b) {
  if (b > a) {
    a = b;
  }
}
void solve() {
  int N;
  cin >> N;
  vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  if (N == 1) {
    cout << A[0] << '\n';
    return;
  }
  tensor<long long, 3> dp({N + 1, 3, 2}, -1e18);
  dp[{0, 0, 1}] = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 2; k++) {
        for (int s : {-1, 1}) {
          bool still = !(i % 2) && s == 1 || i % 2 && s == -1;
          setmax(dp[{i + 1, (j + s + 3) % 3, k & still}],
                 dp[{i, j, k}] + s * A[i]);
        }
      }
    }
  }
  cout << dp[{N, 1, 0}] << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  while (t--) solve();
  return 0;
}
