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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
use std::io::{self, Read};
use std::cmp::max;
use std::collections::LinkedList;


use std::fmt::Display;


// this function prints elements of a vector
fn show<T: std::fmt::Display>(s: &str, v: &Vec<T>) {
    print!("{}: ", s);
    for i in v {
        print!("{} ", i);
    }
    println!();
}

fn show2<T: std::fmt::Display>(s: &str, v: &LinkedList<T>) {
    print!("{}: ", s);
    for i in v {
        print!("{} ", i);
    }
    println!();
}

fn get_deque(input: &Vec<i32>, l: i32, r: i32) -> LinkedList<i32> {
    let mut dl: LinkedList<i32> = LinkedList::new();
    for i in l..r {
        if dl.is_empty() || input[i as usize] > input[*dl.back().unwrap() as usize] {
            dl.push_back(i);
        }
    }
    return dl;
}

fn main() {
    let mut input: Vec<i32> = Vec::new();
    for line in io::stdin().lines() {
        input = line.unwrap().split_whitespace().map(|x| x.parse::<i32>().unwrap() as i32).collect();
    }
    let n: i32 = input.len().try_into().unwrap();
    for i in 0..n-1 {
        input.push(input[i as usize]);
    }
    // show("input", &input);
    let mut hill: LinkedList<i32> = get_deque(&input, 0, n);
    // show2("hill", &hill);

    let mut best: i32 = hill.len().try_into().unwrap();
    for i in 1..n {
        if input[(i+n-1) as usize] > input[*hill.back().unwrap() as usize] {
            hill.push_back(i+n-1);
        }
        if *hill.front().unwrap() == i-1 {
            hill.pop_front();
            // println!("{} ", *hill.front().unwrap());
            let mut lefthill: LinkedList<i32> = get_deque(&input, i, if hill.is_empty() {i+n} else {*hill.front().unwrap()});
            // show2("lefthill", &lefthill);
            // show2("hill", &hill);
            lefthill.append(&mut hill);
            hill = lefthill;
        }
        best = max(best, hill.len().try_into().unwrap());
    }
    println!("{}", best);
}