fn main() {
    println!("Hello, world!!");
}

// estisさんのやつがベース
struct<T> SegmentTree {
    e: u64,
    size: usize,
    tree: Vec<u64>,
    cmpfn: T,
}
impl<T> SegmentTree<T> where T: Fn(u64, u64) -> u64 {
    /// 値の初期化
    pub fn new(n: usize, e: u64, arr: &[u64], cmpfn: fn(u64, u64) -> u64) -> SegmentTree {
        let mut size: usize = 1;
        while size < n  {
            size <<= 1;
        }
        let mut tree: Vec<u64> = Vec::<u64>::with_capacity(2*size);
        for _ in 0..2*size {
            tree.push(e);
        }
        for (i, val) in arr.iter().enumerate() {
            tree[size + i] = *val;
        }

        for i in (1..size).map(|x| size-x) {
            tree[i] = cmpfn(tree[2*i], tree[2*i+1]);
        }

        SegmentTree{
            e,
            size,
            tree,
            cmpfn,
        }
    }

    /// indexの値をnumで更新する.
    pub fn update_number(&mut self, mut index: usize, num: u64) {
        self.tree[index + self.size] = num;
        index = (index + self.size) / 2;
        while index > 0 {
            self.tree[index] = (self.cmpfn)(self.tree[2*index], self.tree[2*index+1]);
            index >>= 1;
        }
    }

    /// [l, r)での範囲の答えを得る.
    pub fn get(&self, l: usize, r:usize) -> u64 {
        // println!("{}, {}, {}", self.size, l, r);
        self.rec(0,self.size,l,r)
    }

    fn rec(&self, min: usize, max: usize, l: usize, r:usize) -> u64 {
        let mid = (min + max)/2;
        if l == min && r == max {
            return self.tree[self.size/(r-l) + l/(r-l)];
        }

        if l < mid && mid < r{
            (self.cmpfn)(self.rec(min, mid, l, mid) , self.rec(mid, max, mid, r))
        }else if mid <= l {
            self.rec(mid, max, l, r)
        }else if r <= mid {
            self.rec(min, mid, l, r)
        }else{
            0
        }
    }

    fn debug(&self){
        println!("{:?}", self.tree);
    }
}