#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  string s;
  cin >> s;

  set<ll> mi;
  rep(i, 26) mi.insert(i);

  ll n = s.size();
  string ans = "";
  rep(i, n) {
    ll idx = s[i] - 'a';
    if (mi.find(idx) != mi.end()) {
      mi.erase(idx);
      ans += s[i];
    } else {
      auto citr = mi.begin();
      ans += *citr + 'a';
      mi.erase(citr);
    }
  }  // i

  if (s == ans) {
    if (!mi.empty()) {
      rep(i, 26) {}
      ans += *mi.begin() + 'a';
    } else {
      vector<char> tst;
      rep(i, 26) tst.push_back(s[i]);
      next_permutation(tst.begin(), tst.end());
      string cmp = "";
      for (char c : tst) cmp += c;
      if (cmp < s) {
        puts("-1");
        return 0;
      } else {
        rep(i,26) if(ans[i] != cmp[i]){
          ans = cmp.substr(0, i+1);
          break;
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}

#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 2100100100;
const int MOD = 1e9 + 7;

int N;

int main() {
    cin >> N;
    vector<ll> A(N);
    vector<ll> sum(N + 1, 0);  // sum[i+1] := A[i] までの和
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
        sum[i + 1] = sum[i] + A[i];
    }

    ll P, Q, R, S;
    ll ans = 1e18;
    for (int i = 2; i <= N - 2; i++) {  // [0,i) と[i,N) に分ける
        // [0,id) と [id, i)
        int id = lower_bound(ALL(sum), sum[i] / 2) - sum.begin();
        if (i - id < 1) {
            id--;
        } else {
            if (abs(sum[i] - sum[id - 1] * 2) < abs(sum[i] - sum[id] * 2)) id--;
        }
        P = sum[id];
        Q = sum[i] - sum[id];

        // [i, id2) と[id2, N)
        int id2 = lower_bound(ALL(sum), (sum[N] - sum[i]) / 2 + sum[i]) - sum.begin();
        if (N - id2 < 1) {
            id2--;
        } else {
            if (abs((sum[N] - sum[id2 - 1]) - (sum[id2 - 1] - sum[i])) < abs((sum[N] - sum[id2]) - (sum[id2] - sum[i]))) id2--;
        }
        R = sum[N] - sum[id2];
        S = sum[id2] - sum[i];
        //cout << 0 << " " << id << " " << i << " " << id2 << " " << N << " " << P << " " << Q << " " << R << " " << S << " " << ans << endl;
        chmin(ans, max(P, max(Q, max(R, S))) - min(P, min(Q, min(R, S))));
    }
    cout << ans << endl;

    return 0;
}
