1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
use std::collections::BTreeMap;

fn main() {
    let mut lines = std::io::stdin().lines().map(|x| x.unwrap());
    let n = lines.next().unwrap().parse::<usize>().unwrap();
    let a = lines
        .next()
        .unwrap()
        .split_whitespace()
        .enumerate()
        .map(|(i, x)| (-x.parse::<i32>().unwrap(), i))
        .collect::<Vec<_>>();
    let mut b = a.clone();
    b.sort();
    let first_non_top = b.iter().position(|p| p.0 != b[0].0).unwrap_or(n);
    let (tops, non_tops) = b.split_at(first_non_top);
    let mut sections = tops
        .iter()
        .map(|(_, i)| ((i + 1) % n, (1, b[0].0)))
        .collect::<BTreeMap<_, _>>();
    // eprintln!("{:?} {:?} {:?}", tops, non_tops, sections);
    for (_, i) in non_tops {
        let (prev_i, (prev_amount, prev_value)) = {
            let pair = sections
                .range(..=*i)
                .last()
                .unwrap_or_else(|| sections.iter().last().unwrap());
            (*pair.0, *pair.1)
        };
        if sections.contains_key(&((i + 1) % n)) {
            // eprintln!("ding");
        }
        sections.insert((i + 1) % n, (prev_amount, prev_value));
        if prev_value != a[*i].0 {
            let (amount, value) = sections.get_mut(&prev_i).unwrap();
            *value = a[*i].0;
            *amount += 1;
        }
        // eprintln!("{} {{{}: ({}, {})}} {} {:?}", i, prev_i, prev_amount, prev_value, a[*i].0, sections);
    }
    println!("{}", sections.into_values().max().unwrap().0);
}