use std::collections::*; fn getline() -> String { let mut ret = String::new(); std::io::stdin().read_line(&mut ret).unwrap(); ret } #[derive(Debug)] struct Stat { l: usize, r: usize, unique: BTreeSet, // index freq: HashMap>, } fn split(a: &[u32], mut s: Stat, idx: usize) -> (Stat, Stat) { let val = a[idx]; assert_eq!(s.freq[&val].len(), 1); s.freq.remove(&val); s.unique.remove(&idx); let mut new = Stat { l: s.l, r: s.r, unique: BTreeSet::new(), freq: HashMap::new(), }; if 2 * idx >= s.l + s.r { for i in idx + 1..s.r { let f = a[i]; let entry = s.freq.get_mut(&f).unwrap(); entry.remove(&i); if entry.is_empty() { s.unique.remove(&i); } if entry.len() == 1 { let &only = entry.iter().next().unwrap(); s.unique.insert(only); } let entry = new.freq.entry(f).or_insert(BTreeSet::new()); if entry.is_empty() { new.unique.insert(i); } else if entry.len() == 1 { let &only = entry.iter().next().unwrap(); new.unique.remove(&only); } entry.insert(i); } new.l = idx + 1; s.r = idx; return (s, new); } for i in s.l..idx { let f = a[i]; let entry = s.freq.get_mut(&f).unwrap(); entry.remove(&i); if entry.is_empty() { s.unique.remove(&i); } if entry.len() == 1 { let &only = entry.iter().next().unwrap(); s.unique.insert(only); } let entry = new.freq.entry(f).or_insert(BTreeSet::new()); if entry.is_empty() { new.unique.insert(i); } else if entry.len() == 1 { let &only = entry.iter().next().unwrap(); new.unique.remove(&only); } entry.insert(i); } new.r = idx; s.l = idx + 1; (new, s) } fn rec(a: &[u32], mut s: Stat) -> i32 { // eprintln!("stat = {s:?}"); let mut ans = 0; while let Some(&idx) = s.unique.first() { let (t, tmp) = split(a, s, idx); ans += rec(a, t) + 1; s = tmp; } // eprintln!("stat = {s:?}, ans = {ans}"); ans } // https://yukicoder.me/problems/no/3258 (3.5) fn main() { getline(); let f = getline().trim().split_whitespace() .map(|x| x.parse::().unwrap()) .collect::>(); let n = f.len(); let mut freq = HashMap::new(); for i in 0..n { freq.entry(f[i]).or_insert(BTreeSet::new()).insert(i); } let stat = Stat { l: 0, r: n, unique: { let mut x = BTreeSet::new(); for i in 0..n { if freq[&f[i]].len() == 1 { x.insert(i); } } x }, freq, }; println!("{}", if rec(&f, stat) % 2 == 1 { "Alice" } else { "Bob" }); }