func_code_string: #define y1 askjdkasldjlkasd   #include <bits/stdc++.h>   #undef y1      using namespace std;      #define pb push_back   #define mp make_pair   #define fi(a, b) for(int i=a; i<=b; i++)   #define fj(a, b) for(int j=a; j<=b; j++)   #define fo(a, b) for(int o=a; o<=b; o++)   #define fdi(a, b) for(int i=a; i>=b; i--)   #define fdj(a, b) for(int j=a; j>=b; j--)   #define fdo(a, b) for(int o=a; o>=b; o--)   #define sz(x) (int)x.size()      typedef long long ll;   typedef long double ld;   typedef vector<int> vi;   typedef pair<int, int> pii;   typedef vector<pii> vpii;   typedef pair<ll, ll> pll;   typedef vector<pll> vpll;   typedef vector<ll> vll;      #ifdef LOCAL   #define err(...) fprintf(stderr, __VA_ARGS__)   #else   #define err(...) while (0)   #endif      double START_TIME;      void exit() {   #ifdef LOCAL     cerr <<  TIME:   << setprecision(5) << fixed << (clock() - START_TIME) / CLOCKS_PER_SEC << endl;   #endif     exit(0);   }      template<typename A, typename B>   ostream& operator<<(ostream& os, pair<A, B> p) {    os <<  (  << p.first <<  ,   << p.second <<  ) ;    return os;   }      template<typename T>   ostream& operator<<(ostream& os, vector<T> v) {    fi(0, sz(v) - 1) {     os << v[i] <<    ;    }    return os;   }      template<typename T>   ostream& operator<<(ostream& os, set<T> t) {    for (auto z : t) {     os << z <<    ;    }    return os;   }      template<typename T1, typename T2>   ostream& operator<<(ostream& os, map<T1, T2> t) {    cerr << endl;    for (auto z : t) {     os <<   t  << z.first <<   ->   << z.second << endl;    }    return os;   }      #ifdef LOCAL   #define dbg(x) {cerr << __LINE__ <<   t  << #x <<  :   << x << endl;}   #define dbg0(x, n) {cerr << __LINE__ <<   t  << #x <<  :  ; for (int ABC = 0; ABC < n; ABC++) cerr << x[ABC] <<    ; cerr << endl;}   #else   #define dbg(x) while(0){}   #define dbg0(x, n) while(0){}   #endif      #ifdef LOCAL   #define ass(x) if (!(x)) { cerr << __LINE__ <<   tassertion failed:   << #x << endl, abort(); }   #else   #define ass(x) assert(x)   #endif      ///////////////////////////////////////////////////      const int MAX = 1e5 + 41;      int n;   int a[MAX];   int l[MAX];   int r[MAX];   int q[MAX];      vpii vd, vs;      bool bad() {    vi cnt(n + 1, 0);    fi(1, n) cnt[a[i]]++;    int mx = *max_element(cnt.begin(), cnt.end());    return (mx > (n + 1) / 2);   }      void clear() {    fi(1, n) l[i] = r[i] = -1;    vd.clear();    vs.clear();   }      void combine(int x, int y) {    r[x] = y;    l[y] = x;   }      void rot(int x) {     while (x != -1) {     int y = r[x];     swap(l[x], r[x]);     x = y;    }    }      void findchains() {     int l = 1;    fi(2, n) {     if (a[i] == a[i - 1]) {      int x = l;      int y = i - 1;      if (a[x] == a[y]) {       vs.pb(mp(x, y));      } else {       vd.pb(mp(x, y));      }      l = i;     } else {      combine(i - 1, i);     }    }    if (a[n] == a[l]) {     vs.pb(mp(l, n));    } else {     vd.pb(mp(l, n));    }   }      void combinediff() {    fi(1, sz(vd) - 1) {     int x = a[vd[i - 1].second];     int y = a[vd[i].first];       if (x == y) {      rot(vd[i].first);      swap(vd[i].first, vd[i].second);        }   //  dbg(vd);   //  combine(vd[i - 1].second, vd[i].first);    }    }      vi getposesforvalue(int x, int val) {    vi res;    while (true) {     int y = r[x];     if (y == -1) break;     if (a[x] != val && a[y] != val) {      res.pb(x);     }     x = y;    }    return res;   }      void combinesame() {   /*    dbg(vs);    dbg(vd);    dbg0(l, n + 1);    dbg0(r, n + 1);   */    set<pii> t;    vi cnt(n + 1, 0);    for (auto z : vs) {     cnt[a[z.first]]++;    }    vector<vpii> v(n + 1, vpii(0, mp(0, 0)));    for (auto z : vs) v[a[z.first]].pb(z);    fi(1, n) if (cnt[i] > 0) t.insert(mp(cnt[i], i));   // dbg(t);   // dbg(cnt);     while (sz(t) > 1 && (*t.rbegin()).first > 1) {          pii v1 = (*t.rbegin());     t.erase(t.find(v1));     pii v2 = (*t.rbegin());     t.erase(t.find(v2));     cnt[v1.second] -= 1;     cnt[v2.second] -= 1;          pii A = v[v1.second].back();     v[v1.second].pop_back();     pii B = v[v2.second].back();     v[v2.second].pop_back();     pii C = v[v1.second].back();     v[v1.second].pop_back();     combine(A.second, B.first);     combine(B.second, C.first);   //  err( COMBINE %d %d ; %d %d ; %d %d n , A.first, A.second, B.first, B.second, C.first, C.second);     v[v1.second].pb(mp(A.first, C.second));     t.insert(mp(cnt[v1.second], v1.second));       if (cnt[v2.second] > 0) {      t.insert(mp(cnt[v2.second], v2.second));     }   //  dbg(cnt);   //  dbg(t);    }                if (sz(t) > 0) {     if (sz(t) > 1) {   //   err( V0 n );       int lst = -1;       int l = -1;           for (auto z : t) {             if (lst == -1) {         lst = v[z.second].back().second;         l = v[z.second].back().first;        } else {         combine(lst, v[z.second].back().first);         lst = v[z.second].back().second;        }            }       if (sz(vd) > 0) {        fi(1, sz(vd) - 1) {         combine(vd[i - 1].second, vd[i].first);        }        if (a[vd.back().second] == a[l]) {         rot(l);               swap(l, lst);        }        combine(vd.back().second, l);       }        } else {   //   err( V1 n );      vpii all, vsame = v[(*t.begin()).second];         fi(0, sz(vd) - 1) {       //    dbg(all);       if (sz(vsame) > 0) {        if (sz(all) == 0 || a[all.back().second] != a[vsame.back().first]) {         all.pb(vsame.back());         vsame.pop_back();        }       }   //    err( BEFORE ROT: n );   //     dbg0(l, n + 1);   //    dbg0(r, n + 1);       if (sz(all) > 0 && a[all.back().second] == a[vd[i].first]) {        rot(vd[i].first);        swap(vd[i].first, vd[i].second);            }           all.pb(vd[i]);   //    err( AFTER ROT: n );   //    dbg0(l, n + 1);   //    dbg0(r, n + 1);   //    dbg(all);      }                  if (sz(all) > 0 && sz(vsame) > 0 && a[all.back().second] != a[vsame.back().first]) {       all.pb(vsame.back());       vsame.pop_back();      }      fi(1, sz(all) - 1) {       combine(all[i - 1].second, all[i].first);      }                  //   dbg(all);      if (sz(vsame) > 0) {                  err( V2 n );           if (sz(all) > 0) {        vsame.pb(mp(all[0].first, all.back().second));            }       //    dbg(vsame);       vector<vi> vp(sz(vsame), vi(0, 0));       fi(0, sz(vsame) - 1) {        vp[i] = getposesforvalue(vsame[i].first, a[vsame[0].first]);   //     err( i = %d size = %d n , i, sz(vp[i]));       }   //    dbg(vsame);   //    dbg(vp);       vi tocomb;           fi(0, sz(vsame) - 1) {        if (sz(tocomb) > 0 && sz(vp[tocomb.back()]) > 0) {         int l1 = vp[tocomb.back()].back();         vp[tocomb.back()].pop_back();         int r1 = vsame[i].first;         int l2 = vsame[i].second;         int r2 = r[l1];         combine(l1, r1);               combine(l2, r2);         vp[tocomb.back()].insert(vp[tocomb.back()].begin(), vp[i].begin(), vp[i].end());              } else {         while (sz(vp[i]) > 0 && sz(tocomb) > 0) {          int l1 = vp[i].back();          vp[i].pop_back();          int r1 = vsame[tocomb.back()].first;          int l2 = vsame[tocomb.back()].second;          int r2 = r[l1];   //       err( TO COMB %d %d; %d %d n , l1, r1, l2, r2);   //       dbg0(l, n + 1);   //       dbg0(r, n + 1);          tocomb.pop_back();          combine(l1, r1);          combine(l2, r2);                }         tocomb.pb(i);              }       }          }     }    } else {   //  err( VA n );   //  dbg(vd);     fi(1, sz(vd) - 1) {       combine(vd[i - 1].second, vd[i].first);      }    }   }      void printans() {    int st = -1;    fi(1, n) if (l[i] == -1) st = i;    if (st == -1) {     err( st = %d n , st);     assert(false);    }   /*    err( ans: n );    dbg0(l, n + 1);     dbg0(r, n + 1);   */    int ans = 0;    vi res;    while (st != -1) {   //  err( %d  , st);     res.pb(st);     st = r[st];    }   // err(  n );       if (sz(res) < n) {     err( size = %d n , sz(res));     assert(false);    }    fi(1, sz(res) -1 ) {     ans += (abs(res[i - 1] - res[i]) > 1 ? 1 : 0);     if (a[res[i]] == a[res[i - 1]]) {      err( same neigh! n );      assert(false);     }    }    //dbg(res);    printf( %d n , ans);   }      void solve () {    if (n == 1) {     printf( 0 n );     return;    }    if (bad()) {     printf( -1 n );     return;    }    clear();    findchains();     combinediff();     combinesame();   /*    dbg(  );    dbg(vd);    dbg(vs);    dbg0(l, n + 1);    dbg0(r, n + 1);   */    printans();   }      int main() {   #ifdef LOCAL    freopen( input.txt ,  r , stdin);    freopen( output.txt ,  w , stdout);    START_TIME = (double)clock();   #endif        int t;    scanf( %d , &t);    while (t--) {     scanf( %d , &n);       fi(1, n) scanf( %d , &a[i]);     solve();    }       exit();    return 0;   }            