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 facil(a: &[u32], l: usize, r: usize) -> Stat { let b = &a[l..r]; let mut freq = HashMap::new(); for &f in b { *freq.entry(f).or_insert(0) += 1; } let stat = Stat { l, r, unique: { let mut x = BTreeSet::new(); for i in l..r { if freq[&a[i]] == 1 { x.insert(i); } } x }, freq, }; stat } fn split(a: &[u32], mut s: Stat, idx: usize) -> (Stat, Stat) { let val = a[idx]; assert_eq!(s.freq[&val], 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 c = s.freq.get(&f).cloned().unwrap_or(0); if c > 0 { *s.freq.get_mut(&f).unwrap() -= 1; if c == 1 { s.freq.remove(&f); s.unique.remove(&i); } if c == 2 { s.unique.insert(i); } } let c = new.freq.get(&f).cloned().unwrap_or(0); *new.freq.entry(f).or_insert(0) += 1; if c == 0 { new.unique.insert(i); } else if c == 1 { new.unique.remove(&i); } } new.l = idx + 1; s.r = idx; return (s, new); } for i in s.l..idx { let f = a[i]; let c = s.freq.get(&f).cloned().unwrap_or(0); if c > 0 { *s.freq.get_mut(&f).unwrap() -= 1; if c == 1 { s.freq.remove(&f); s.unique.remove(&i); } if c == 2 { s.unique.insert(i); } } let c = new.freq.get(&f).cloned().unwrap_or(0); *new.freq.entry(f).or_insert(0) += 1; if c == 0 { new.unique.insert(i); } else if c == 1 { new.unique.remove(&i); } } new.r = idx; s.l = idx + 1; (new, s) } fn rec(a: &[u32], mut s: Stat) -> i32 { let n = a.len(); let mut seen = s.l; 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; seen = idx + 1; } // 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 &f in &f { *freq.entry(f).or_insert(0) += 1; } let stat = Stat { l: 0, r: n, unique: { let mut x = BTreeSet::new(); for i in 0..n { if freq[&f[i]] == 1 { x.insert(i); } } x }, freq, }; println!("{}", if rec(&f, stat) % 2 == 1 { "Alice" } else { "Bob" }); }