#![allow(unused_imports, non_snake_case)] #![allow(dead_code)] use crate::scanner::Scanner; use crate::{data_structure::counter::Counter, misc::run_length_encoding}; fn main() { let mut scan = Scanner::new(); let _n = scan.read::(); let a = scan .read_line() .split_ascii_whitespace() .map(|s| s.parse::().unwrap()) .collect(); let r = run_length_encoding(&a).map(|t| t.1); let cnt = r.to::>(); if r.ilen() == 1 { println!("0"); return; } if r[0] == *r.last_exn() && r.part(1..r.ilen() - 1) .into_iter() .collect::>() .values() .all(|x| *x == 1) { println!("1"); return; } if cnt.values().all(|x| *x == 1) { println!("0"); return; } println!("-1"); } pub mod arraylist { use crate::{ext::range::IntRangeBounds, independent::integer::Int}; use std::fmt::Formatter; use std::iter::FromIterator; use std::ops::{Index, IndexMut, RangeBounds}; use std::slice::Iter; #[derive(Clone, PartialEq, Eq)] pub struct List { pub vec: Vec, } impl List { #[inline] pub fn new() -> List { List { vec: vec![] } } #[inline] pub fn init(init: T, n: i32) -> List where T: Clone, { List { vec: vec![init; n as usize], } } #[inline] pub fn from_vec(vec: Vec) -> List { List { vec } } #[inline] pub fn ilen(&self) -> i32 { self.vec.len() as i32 } #[inline] pub fn iter(&self) -> Iter<'_, T> { self.vec.iter() } #[inline] pub fn push(&mut self, item: T) { self.vec.push(item); } #[inline] pub fn sort(&mut self) where T: Ord, { self.vec.sort(); } #[inline] pub fn reverse(&mut self) { self.vec.reverse(); } #[inline] pub fn sort_by(&mut self, compare: F) where F: FnMut(&T, &T) -> std::cmp::Ordering, { self.vec.sort_by(compare) } #[inline] pub fn sort_by_key(&mut self, compare: F) where F: FnMut(&T) -> K, K: Ord, { self.vec.sort_by_key(compare) } #[inline] pub fn first(&self) -> Option<&T> { self.vec.first() } #[inline] pub fn last(&self) -> Option<&T> { self.vec.last() } #[inline] pub fn pop(&mut self) -> Option { self.vec.pop() } #[inline] pub fn swap(&mut self, i: i32, j: i32) { self.vec.swap(i as usize, j as usize); } #[inline] pub fn append(&mut self, mut other: Self) { self.vec.append(&mut other.vec); } #[inline] pub fn extend(&mut self, other: impl Iterator) { self.vec.extend(other); } #[inline] pub fn mirror(&self) -> std::iter::Cloned> where T: Clone, { self.iter().cloned() } #[inline] pub fn map(&self, f: F) -> List where T: Clone, F: FnMut(T) -> B, { self.mirror().map(f).collect() } #[inline] pub fn filter

(&self, predicate: P) -> List where T: Clone, P: FnMut(&T) -> bool, { self.mirror().filter(predicate).collect() } #[inline] pub fn filter_map(&self, f: F) -> List where T: Clone, F: FnMut(T) -> Option, { self.mirror().filter_map(f).collect() } #[inline] pub fn any

(&self, predicate: P) -> bool where P: FnMut(&T) -> bool, { self.iter().any(predicate) } #[inline] pub fn all

(&self, predicate: P) -> bool where P: FnMut(&T) -> bool, { self.iter().all(predicate) } #[inline] pub fn sum(&self) -> T where T: Int, { self.iter().cloned().fold(T::zero(), |acc, x| acc + x) } #[inline] pub fn enumerate(&self) -> List<(i32, T)> where T: Clone, { self.mirror() .enumerate() .map(|p| (p.0 as i32, p.1)) .collect() } #[inline] pub fn find

(&self, mut predicate: P) -> Option<&T> where P: FnMut(&T) -> bool, { self.iter().find(|x| predicate(*x)) } #[inline] pub fn index_of

(&self, mut predicate: P) -> Option where P: FnMut(&T) -> bool, { self.iter() .enumerate() .find(|&(_i, x)| predicate(x)) .map(|p| p.0 as i32) } #[inline] pub fn to>(&self) -> B where T: Clone, { self.mirror().collect() } #[inline] pub fn min(&self) -> Option<&T> where T: Ord, { self.iter().min() } #[inline] pub fn max(&self) -> Option<&T> where T: Ord, { self.iter().max() } #[inline] pub fn argmin(&self) -> Option where T: Ord, { let item = self.iter().min()?; self.iter() .enumerate() .find(|p| p.1 == item) .map(|p| p.0 as i32) } #[inline] pub fn argmax(&self) -> Option where T: Ord, { let item = self.iter().max()?; self.iter() .enumerate() .find(|p| p.1 == item) .map(|p| p.0 as i32) } #[inline] pub fn part(&self, range: U) -> List where T: Clone, U: RangeBounds, { List::from_vec( self.vec[range.lower_bound(0) as usize..range.upper_bound(self.ilen()) as usize] .to_vec(), ) } #[inline] pub fn first_exn(&self) -> &T { self.first().unwrap() } #[inline] pub fn last_exn(&self) -> &T { self.last().unwrap() } #[inline] pub fn pop_exn(&mut self) -> T { self.pop().unwrap() } #[inline] pub fn min_exn(&self) -> &T where T: Ord, { self.min().unwrap() } #[inline] pub fn max_exn(&self) -> &T where T: Ord, { self.max().unwrap() } #[inline] pub fn argmin_exn(&self) -> i32 where T: Ord, { self.argmin().unwrap() } #[inline] pub fn argmax_exn(&self) -> i32 where T: Ord, { self.argmax().unwrap() } #[inline] pub fn find_exn

(&self, predicate: P) -> &T where P: FnMut(&T) -> bool, { self.find(predicate).unwrap() } #[inline] pub fn index_of_exn

(&self, predicate: P) -> i32 where P: FnMut(&T) -> bool, { self.index_of(predicate).unwrap() } } impl Index for List { type Output = T; #[inline] fn index(&self, index: i32) -> &Self::Output { if cfg!(debug_assertions) { self.vec.index(index as usize) } else { unsafe { self.vec.get_unchecked(index as usize) } } } } impl IndexMut for List { #[inline] fn index_mut(&mut self, index: i32) -> &mut Self::Output { if cfg!(debug_assertions) { self.vec.index_mut(index as usize) } else { unsafe { self.vec.get_unchecked_mut(index as usize) } } } } impl FromIterator for List { fn from_iter>(iter: U) -> Self { let mut vec = vec![]; for i in iter { vec.push(i); } List { vec } } } impl IntoIterator for List { type Item = T; type IntoIter = std::vec::IntoIter; fn into_iter(self) -> std::vec::IntoIter { self.vec.into_iter() } } impl<'a, T> IntoIterator for &'a List { type Item = &'a T; type IntoIter = Iter<'a, T>; fn into_iter(self) -> Iter<'a, T> { self.vec.iter() } } impl std::fmt::Display for List { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { write!( f, "{}", self.iter() .map(|x| format!("{}", x)) .collect::>() .join(" ") ) } } impl std::fmt::Debug for List { fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { write!( f, "[{}]", self.iter() .map(|x| format!("{:?}", x)) .collect::>() .join(", ") ) } } impl From> for List { fn from(vec: Vec) -> Self { Self::from_vec(vec) } } impl From<&[T]> for List { fn from(slice: &[T]) -> Self { slice.iter().cloned().collect() } } #[macro_export] macro_rules ! list { ( ) => { $ crate :: arraylist :: List :: new ( ) } ; ( $ init : expr ; $ ( $ dim : expr ) ;* ) => { list ! ( $ ( $ dim ) ;* => $ init ) } ; ( $ head : expr ; $ ( $ tail : expr ) ;* => $ init : expr ) => { $ crate :: arraylist :: List :: init ( list ! ( $ ( $ tail ) ;* => $ init ) , $ head ) } ; ( $ head : expr => $ init : expr ) => { $ crate :: arraylist :: List :: init ( $ init , $ head ) } ; } } pub mod independent { pub mod integer { pub trait Int: std::ops::Add + std::ops::Sub + std::ops::Mul + std::ops::Div + std::ops::Rem + std::hash::Hash + PartialEq + Eq + PartialOrd + Ord + Copy { fn to_u8(&self) -> u8; fn to_u16(&self) -> u16; fn to_u32(&self) -> u32; fn to_u64(&self) -> u64; fn to_u128(&self) -> u128; fn to_i8(&self) -> i8; fn to_i16(&self) -> i16; fn to_i32(&self) -> i32; fn to_i64(&self) -> i64; fn to_i128(&self) -> i128; fn to_usize(&self) -> usize; fn to_isize(&self) -> isize; fn zero() -> Self; fn one() -> Self; } macro_rules ! impl_integer_functions { ( $ ( $ name : ident , $ tpe : ident ) ,* ) => { $ ( fn $ name ( & self ) -> $ tpe { * self as $ tpe } ) * } ; } macro_rules ! impl_integer { ( $ ( $ tpe : ident ) ,* ) => { $ ( impl Int for $ tpe { impl_integer_functions ! ( to_u8 , u8 , to_u16 , u16 , to_u32 , u32 , to_u64 , u64 , to_u128 , u128 , to_i8 , i8 , to_i16 , i16 , to_i32 , i32 , to_i64 , i64 , to_i128 , i128 , to_usize , usize , to_isize , isize ) ; fn zero ( ) -> Self { 0 } fn one ( ) -> Self { 1 } } ) * } ; } impl_integer!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize); } } pub mod scanner { use crate::arraylist::List; use std::io::{stdin, BufReader, Bytes, Read, Stdin}; use std::str::FromStr; pub struct Scanner { buf: Bytes>, } impl Scanner { pub fn new() -> Scanner { Scanner { buf: BufReader::new(stdin()).bytes(), } } pub fn read_next(&mut self) -> Option { let token = self .buf .by_ref() .map(|c| c.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect::(); token.parse::().ok() } pub fn read_line(&mut self) -> String { self.buf .by_ref() .map(|c| c.unwrap() as char) .skip_while(|c| *c == '\n') .take_while(|c| *c != '\n') .collect() } pub fn read(&mut self) -> T { self.read_next().unwrap() } pub fn readn(&mut self, n: i32) -> List { (0..n).map(|_| self.read::()).collect() } pub fn chars(&mut self) -> List { self.read::().chars().collect() } } } pub mod misc { use crate::arraylist::List; use crate::independent::integer::Int; use std::collections::{BTreeSet, HashMap}; pub const CONST_1E9_7: i64 = 1_000_000_007; pub fn rep<'a, S, T>(n: i32, mut f: S) -> List where S: FnMut() -> T + 'a, { (0..n).map(|_| f()).collect::>() } pub fn adjacent4(y: i32, x: i32, h: i32, w: i32) -> impl Iterator { const DYDX: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)]; DYDX.iter().filter_map(move |&(dy, dx)| { let ny = y + dy; let nx = x + dx; if nx >= 0 && nx < w && ny >= 0 && ny < h { Some((ny, nx)) } else { None } }) } pub fn adjacent8(y: i32, x: i32, h: i32, w: i32) -> impl Iterator { const DYDX: [(i32, i32); 8] = [ (-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1), ]; DYDX.iter().filter_map(move |&(dy, dx)| { let ny = y + dy; let nx = x + dx; if nx >= 0 && nx < w && ny >= 0 && ny < h { Some((ny, nx)) } else { None } }) } pub fn run_length_encoding(slice: &List) -> List<(i64, T)> { slice.mirror().fold(List::new(), |mut acc, x| { if let Some((cnt, item)) = acc.pop() { if item == x { acc.push((cnt + 1, x)); } else { acc.push((cnt, item)); acc.push((1, x)); } } else { acc.push((1, x)); } acc }) } pub fn indices_by_elem( slice: &List, ) -> std::collections::HashMap> { let mut hmap = std::collections::HashMap::new(); for i in 0..slice.ilen() { hmap.entry(slice[i].clone()).or_insert(List::new()).push(i); } hmap } pub fn combine>( left: &[S], right: &[T], ) -> U { let mut ret = vec![]; for i in 0..left.len() { for j in 0..right.len() { ret.push((left[i].clone(), right[j].clone())); } } ret.into_iter().collect::() } pub fn split(slice: &List, sep: T) -> List> { slice .iter() .fold(List::from(vec![List::new()]), |mut acc, x| { if x == &sep { acc.push(List::new()); acc } else { let last = acc.ilen() - 1; acc[last].push(x.clone()); acc } }) } pub fn join(slice: &List, sep: &str) -> String { let strings = slice.iter().map(|t| format!("{}", t)).collect::>(); strings.join(sep) } pub fn coord_comp(slice: &List) -> (List, HashMap) { let mut set = BTreeSet::new(); for &item in slice { set.insert(item); } let mut hmap = HashMap::new(); for (i, &v) in set.iter().enumerate() { hmap.insert(v, i as i32); } (set.into_iter().collect::>(), hmap) } pub fn shakutori(n: i32, k: i64, a: &List) -> i32 { let mut sum = 0; let mut right = 0; let mut ret = 0; for left in 0..n { while right < n && sum <= k { sum += a[right]; right += 1; } ret += right - left; if right == left { right += 1; } else { sum -= a[left]; } } ret } pub fn inverse(a: &List, n: i32) -> List { let mut inv = List::init(0, n); for i in 0..a.ilen() { inv[a[i]] = i; } inv } pub fn pow(mut a: i64, mut n: i64) -> i64 { let mut res = 1; while n > 0 { if n & 1 == 1 { res *= a; } a = a * a; n >>= 1; } res } pub fn ceil_div(x: T, y: T) -> T { (x + y - T::one()) / y } pub fn ceil_mod(x: T, y: T) -> T { ceil_div(x, y) * y } pub fn unzip(v: &List<(P, Q)>) -> (List

, List) { ( v.iter().map(|t| t.0.clone()).collect(), v.iter().map(|t| t.1.clone()).collect(), ) } pub fn unzip3( v: &List<(P, Q, R)>, ) -> (List

, List, List) { ( v.iter().map(|t| t.0.clone()).collect(), v.iter().map(|t| t.1.clone()).collect(), v.iter().map(|t| t.2.clone()).collect(), ) } pub fn is_palindrome(chars: &List) -> bool { let s = chars.clone(); let mut t = s.clone(); t.reverse(); (0..s.ilen()).filter(|&i| s[i] == t[i]).count() as i32 == s.ilen() } } pub mod data_structure { pub mod counter { use std::collections::HashMap; use std::hash::Hash; use std::ops::*; #[derive(Clone, Debug)] pub struct Counter { pub cnt: HashMap, pub d: i64, } impl Counter { pub fn new() -> Counter { Counter { cnt: HashMap::new(), d: 0, } } #[doc = " Remove key when the value <= 0"] pub fn dec(&mut self, key: K, delta: i64) { if self.by_ref(&key) - delta <= 0 { self.remove(&key); } else { *self.cnt.get_mut(&key).unwrap() -= delta; } } pub fn by_ref(&self, key: &K) -> i64 { *self.cnt.get(key).unwrap_or(&self.d) } } impl Deref for Counter { type Target = HashMap; fn deref(&self) -> &Self::Target { &self.cnt } } impl DerefMut for Counter { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.cnt } } impl Index for Counter { type Output = i64; fn index(&self, index: K) -> &Self::Output { self.cnt.get(&index).unwrap_or(&self.d) } } impl IndexMut for Counter { fn index_mut(&mut self, index: K) -> &mut i64 { if !self.cnt.contains_key(&index) { self.cnt.insert(index.clone(), self.d); } self.cnt.get_mut(&index).unwrap() } } impl std::iter::FromIterator for Counter { fn from_iter>(iter: T) -> Self { let mut cnt = HashMap::new(); for i in iter { *cnt.entry(i).or_insert(0) += 1; } Counter { cnt, d: 0 } } } impl Add for Counter { type Output = Counter; fn add(self, other: Counter) -> Counter { let mut ret = Counter::new(); for (k, v) in self.iter().chain(other.iter()) { ret[k.clone()] += *v; } ret } } impl AddAssign for Counter { fn add_assign(&mut self, other: Self) { *self = self.clone().add(other); } } } } pub mod ext { pub mod range { use crate::independent::integer::Int; use std::cmp::{max, min}; use std::ops::{Bound, Range, RangeBounds, RangeInclusive}; pub trait RangeEx { fn width(&self) -> T; fn empty(&self) -> bool; fn contain_range(&self, inner: &Self) -> bool; fn separate_range(&self, other: &Self) -> bool; type ReturnRange; fn overlap(&self, other: &Self) -> Self::ReturnRange; } impl RangeEx for Range { fn width(&self) -> T { if self.empty() { T::zero() } else { self.end - self.start } } fn empty(&self) -> bool { !(self.start < self.end) } fn contain_range(&self, inner: &Self) -> bool { self.start <= inner.start && inner.end <= self.end } fn separate_range(&self, other: &Self) -> bool { self.end <= other.start || other.end <= self.start } type ReturnRange = Range; fn overlap(&self, other: &Self) -> Self::ReturnRange { let left = max(self.start, other.start); let right = min(self.end, other.end); left..right } } impl RangeEx for RangeInclusive { fn width(&self) -> T { if self.empty() { T::zero() } else { *self.end() - *self.start() + T::one() } } fn empty(&self) -> bool { !(self.start() <= self.end()) } fn contain_range(&self, inner: &Self) -> bool { self.start() <= inner.start() && inner.end() <= self.end() } fn separate_range(&self, other: &Self) -> bool { self.end() <= other.start() || other.end() <= self.start() } type ReturnRange = RangeInclusive; fn overlap(&self, other: &Self) -> Self::ReturnRange { let left = *max(self.start(), other.start()); let right = *min(self.end(), other.end()); left..=right } } pub trait IntRangeBounds: RangeBounds { #[doc = " inclusive"] fn lower_bound(&self, lower_bound: U) -> U { match self.start_bound() { Bound::Included(x) => max(lower_bound, *x), Bound::Excluded(x) => max(lower_bound, *x + U::one()), Bound::Unbounded => lower_bound, } } #[doc = " exclusive"] fn upper_bound(&self, upper_bound: U) -> U { match self.end_bound() { Bound::Included(x) => min(upper_bound, *x + U::one()), Bound::Excluded(x) => min(upper_bound, *x), Bound::Unbounded => upper_bound, } } fn to_harfopen(&self, lb: U, ub: U) -> Range { self.lower_bound(lb)..self.upper_bound(ub) } } impl IntRangeBounds for T where T: RangeBounds {} } }