;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-int:defconstant-eqx OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))
    #'equal)
  #+swank (ql:quickload '(:cl-debug-print :fiveam) :silent t)
  #-swank (set-dispatch-macro-character
           #\# #\> (lambda (s c p) (declare (ignore c p)) (read s nil nil t))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
;;;
;;; ARRAY-ELEMENT-TYPE is not constant-folded on SBCL version earlier than
;;; 1.5.0. See
;;; https://github.com/sbcl/sbcl/commit/9f0d12e7ab961828931d01c0b2a76a5885ad35d2
;;;

(eval-when (:compile-toplevel :load-toplevel :execute)
  (sb-c:deftransform array-element-type ((array))
    (let ((type (sb-c::lvar-type array)))
      (flet ((element-type (type)
               (and (sb-c::array-type-p type)
                    (sb-int:neq (sb-kernel::array-type-specialized-element-type type) sb-kernel:*wild-type*)
                    (sb-kernel:type-specifier (sb-kernel::array-type-specialized-element-type type)))))
        (cond ((let ((type (element-type type)))
                 (and type
                      `',type)))
              ((sb-kernel:union-type-p type)
               (let (result)
                 (loop for type in (sb-kernel:union-type-types type)
                       for et = (element-type type)
                       unless (and et
                                   (if result
                                       (equal result et)
                                       (setf result et)))
                       do (sb-c::give-up-ir1-transform))
                 `',result))
              ((sb-kernel:intersection-type-p type)
               (loop for type in (sb-kernel:intersection-type-types type)
                     for et = (element-type type)
                     when et
                     return `',et
                     finally (sb-c::give-up-ir1-transform)))
              (t
               (sb-c::give-up-ir1-transform)))))))

;;;
;;; Compute inversion number by merge sort
;;;

(declaim (inline %merge-count))
(defun %merge-count (l mid r source-vec dest-vec predicate key)
  (declare ((integer 0 #.array-total-size-limit) l mid r)
           (function predicate))
  (loop with count of-type (integer 0 #.most-positive-fixnum) = 0
        with i = l
        with j = mid
        for idx from l
        when (= i mid)
        do (loop for j from j below r
                 for idx from idx
                 do (setf (aref dest-vec idx)
                          (aref source-vec j))
                 finally (return-from %merge-count count))
        when (= j r)
        do (loop for i from i below mid
                 for idx from idx
                 do (setf (aref dest-vec idx)
                          (aref source-vec i))
                 finally (return-from %merge-count count))
        do (if (funcall predicate
                        (funcall key (aref source-vec j))
                        (funcall key (aref source-vec i)))
               (setf (aref dest-vec idx) (aref source-vec j)
                     j (1+ j)
                     count (+ count (- mid i)))
               (setf (aref dest-vec idx) (aref source-vec i)
                     i (1+ i)))))

(defmacro with-fixnum+ (form)
  (let ((fixnum+ '(integer 0 #.most-positive-fixnum)))
    `(the ,fixnum+
          ,(reduce (lambda (f1 f2)`(,(car form)
                                   (the ,fixnum+ ,f1)
                                   (the ,fixnum+ ,f2)))
	           (cdr form)))))

(declaim (inline %calc-by-insertion-sort!))
(defun %calc-by-insertion-sort! (vec predicate l r)
  (declare (function predicate)
           ((integer 0 #.array-total-size-limit) l r))
  (loop with inv-count of-type (integer 0 #.most-positive-fixnum) = 0
        for end from (+ l 1) below r
        do (loop for i from end above l
                 while (funcall predicate (aref vec i) (aref vec (- i 1)))
                 do (rotatef (aref vec (- i 1)) (aref vec i))
                    (incf inv-count))
        finally (return inv-count)))

;; NOTE: This function is slow on SBCL version earlier than 1.5.0 as
;; constant-folding of ARRAY-ELEMENT-TYPE doesn't work. Use
;; array-element-type.lisp if necessary.
(declaim (inline count-inversions!))
(defun count-inversions! (vector predicate &key (start 0) end (key #'identity))
  "Calculates the number of the inversions of VECTOR w.r.t. the strict order
PREDICATE. This function sorts VECTOR as a side effect."
  (declare (vector vector)
           (function predicate))
  (let ((end (or end (length vector))))
    (declare ((integer 0 #.array-total-size-limit) start end))
    (assert (<= start end))
    (let ((buffer (make-array end :element-type (array-element-type vector))))
      (labels
          ((recur (l r merge-to-vec1-p)
             (declare (optimize (safety 0))
                      ((integer 0 #.array-total-size-limit) l r))
             (cond ((= l r) 0)
                   ((= (+ l 1) r)
                    (unless merge-to-vec1-p
                      (setf (aref buffer l) (aref vector l)))
                    0)
                   ;; It is faster to use insertion sort. I don't adopt it
                   ;; by default, however, because that makes it hard to
                   ;; change the code to fit some special settings.
                   ;; ((and (<= (- r l) 24) merge-to-vec1-p)
                   ;;  (%calc-by-insertion-sort! vector predicate l r))
                   (t
                    (let ((mid (floor (+ l r) 2)))
                      (with-fixnum+
                          (+ (recur l mid (not merge-to-vec1-p))
                             (recur mid r (not merge-to-vec1-p))
                             (if merge-to-vec1-p
                                 (%merge-count l mid r buffer vector predicate key)
                                 (%merge-count l mid r vector buffer predicate key)))))))))
        (recur start end t)))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;;;
;;; Body
;;;

(declaim (inline to-code))
(defun to-code (c)
  (- (char-code c) #.(char-code #\a)))

(declaim (inline to-char))
(defun to-char (x)
  (code-char (+ x #.(char-code #\a))))

(declaim (inline make-histogram))
(defun make-histogram (s)
  (let ((res (make-array 26 :element-type 'uint32 :initial-element 0)))
    (sb-int:dovector (c s res)
      (incf (aref res (to-code c))))))

(defun solve (s &optional (odd-char #\Nul))
  (declare #.OPT
           (simple-base-string s))
  (let* ((len (length s))
         (len/2-floor (floor len 2))
         (len/2-ceil (ceiling len 2))
         (histo (make-histogram s))
         (histo-dp (make-array 26 :element-type 'uint32 :initial-element 0))
         (seq (make-array len))
         (part1-ord 0)
         (part2-ord len/2-ceil))
    (declare (uint32 part1-ord part2-ord))
    (dotimes (i len)
      (let* ((c (aref s i))
             (code (to-code c)))
        (cond
          ((and (char= odd-char c)
                (= (aref histo-dp code) (floor (aref histo code) 2)))
           (setf (aref seq i) (cons c len/2-floor)))
          ((< (aref histo-dp code) (floor (aref histo code) 2))
           (setf (aref seq i) (cons c part1-ord)
                 part1-ord (+ 1 part1-ord)))
          (t
           (setf (aref seq i) (cons c part2-ord)
                 part2-ord (+ 1 part2-ord))))
        (incf (aref histo-dp code))))
    (let ((count1 (count-inversions! seq
                                     (lambda (x y) (< (the uint32 x) (the uint32 y)))
                                     :key #'cdr))
          (ords (make-array 26 :element-type 'list :initial-element nil)))
      (loop for i from (- len 1) downto len/2-ceil
            for ord from 0 below len/2-floor
            do (push ord (aref ords (to-code (car (aref seq i))))))
      (dotimes (i 26)
        (setf (aref ords i) (nreverse (aref ords i))))
      (let ((seq/2 (make-array len/2-floor :element-type 'uint32)))
        (dotimes (i len/2-floor)
          (let ((c (car (aref seq i))))
            (setf (aref seq/2 i) (pop (aref ords (to-code c))))))
        (let ((count2 (count-inversions! seq/2 #'<)))
          (+ count1 count2))))))

(defun main ()
  (let* ((s (coerce (read-line) 'simple-base-string))
         (len (length s))
         (histo (make-histogram s)))
    (println
     (if (evenp len)
         (if (every #'evenp histo)
             (solve s)
             -1)
         (let ((odd-chars (loop for i below 26
                                for x across histo
                                when (oddp x)
                                collect (to-char i))))
           (if (= (length odd-chars) 1)
               (solve s (car odd-chars))
               -1))))))

#-swank (main)


Measured memory_bytes: 58340