pub use __cargo_equip::prelude::*; use algebraic::{algebra, monoid}; use chminmax::chmax; #[allow(unused_imports)] use proconio::{ input, marker::{Bytes, Chars, Usize1}, }; use segment_tree::SegmentTree; use sliding_window_aggregation::SlidingWindowAggregation; const INF: i64 = 1 << 60; algebra!(M, i64); monoid!(M, -INF, |&a: &i64, &b: &i64| a.max(b)); fn main() { input! { n: usize, k: usize, m: usize, a: [i64; n], } let mut b = vec![0; n + 1]; for i in 0..n { b[i + 1] = b[i] + a[i]; } let mut dp = vec![-INF; n + 1]; dp[0] = 0; for _ in 0..k { let mut dpn = vec![-INF; n + 1]; let mut swag1 = SlidingWindowAggregation::::new(); let mut swag2 = SlidingWindowAggregation::::new(); for i in 0..=n { chmax!(dpn[i], swag1.prod() - b[i]); chmax!(dpn[i], swag2.prod() + b[i]); swag1.push_back(dp[i] + b[i]); swag2.push_back(dp[i] - b[i]); if swag1.len() > m { swag1.pop_front(); swag2.pop_front(); } } dp = dpn; // eprintln!("{:?}", &dp); } println!("{}", dp[n]); } // The following code was expanded by `cargo-equip`. /// # Bundled libraries /// /// - `algebraic 0.1.0 (path+████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::algebraic` /// - `chminmax 0.1.0 (path+████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::chminmax` /// - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT/Apache-2.0` as `crate::__cargo_equip::crates::__lazy_static_1_4_0` /// - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio` /// - `segment-tree 0.1.0 (path+████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::segment_tree` /// - `sliding-window-aggregation 0.1.0 (path+██████████████████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::sliding_window_aggregation` /// /// # License and Copyright Notices /// /// - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)` /// /// ```text /// Copyright (c) 2010 The Rust Project Developers /// /// Permission is hereby granted, free of charge, to any /// person obtaining a copy of this software and associated /// documentation files (the "Software"), to deal in the /// Software without restriction, including without /// limitation the rights to use, copy, modify, merge, /// publish, distribute, sublicense, and/or sell copies of /// the Software, and to permit persons to whom the Software /// is furnished to do so, subject to the following /// conditions: /// /// The above copyright notice and this permission notice /// shall be included in all copies or substantial portions /// of the Software. /// /// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF /// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED /// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A /// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT /// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY /// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION /// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR /// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER /// DEALINGS IN THE SOFTWARE. /// ``` /// /// - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)` /// /// ```text /// The MIT License /// Copyright 2019 (C) statiolake /// /// Permission is hereby granted, free of charge, to any person obtaining a copy of /// this software and associated documentation files (the "Software"), to deal in /// the Software without restriction, including without limitation the rights to /// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of /// the Software, and to permit persons to whom the Software is furnished to do so, /// subject to the following conditions: /// /// The above copyright notice and this permission notice shall be included in all /// copies or substantial portions of the Software. /// /// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR /// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS /// FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR /// COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER /// IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN /// CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. /// /// Copyright for original `input!` macro is held by Hideyuki Tanaka, 2019. The /// original macro is licensed under BSD 3-clause license. /// /// Redistribution and use in source and binary forms, with or without /// modification, are permitted provided that the following conditions are met: /// /// 1. Redistributions of source code must retain the above copyright notice, this /// list of conditions and the following disclaimer. /// /// 2. Redistributions in binary form must reproduce the above copyright notice, /// this list of conditions and the following disclaimer in the documentation /// and/or other materials provided with the distribution. /// /// 3. Neither the name of the copyright holder nor the names of its contributors /// may be used to endorse or promote products derived from this software /// without specific prior written permission. /// /// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND /// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED /// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE /// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE /// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL /// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR /// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER /// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, /// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE /// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. /// ``` #[cfg_attr(any(), rustfmt::skip)] #[allow(unused)] mod __cargo_equip { pub(crate) mod crates { pub mod algebraic {pub use crate::__cargo_equip::macros::algebraic::*;pub trait Algebra{type S;}pub trait Act:Algebra{type X;fn act(f:&Self::S,x:&Self::X)->Self::X;}pub trait Monoid:Algebra{fn e()->Self::S;fn op(x:&Self::S,y:&Self::S)->Self::S;}pub trait Group:Monoid{fn inv(x:&Self::S)->Self::S;}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_algebra{($ident:ident,$ty:ty)=>{#[derive(Clone)]enum$ident{}impl$crate::__cargo_equip::crates::algebraic::Algebra for$ident{type S=$ty;}};}macro_rules!algebra{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_algebra!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_act{($ident:ident,$tar:ty,$act:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Act for$ident{type X=$tar;#[inline]fn act(f:&Self::S,x:&Self::X)->Self::X{$act(f,x)}}};}macro_rules!act{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_act!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_monoid{($ident:ident,$e:expr,$op:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}};}macro_rules!monoid{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_monoid!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_algebraic_group{($ident:ident,$e:expr,$op:expr,$inv:expr)=>{impl$crate::__cargo_equip::crates::algebraic::Monoid for$ident{#[inline]fn e()->Self::S{$e}#[inline]fn op(x:&Self::S,y:&Self::S)->Self::S{$op(x,y)}}impl$crate::__cargo_equip::crates::algebraic::Group for$ident{#[inline]fn inv(x:&Self::S)->Self::S{$inv(x)}}};}macro_rules!group{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_algebraic_group!{$($tt)*})}} pub mod chminmax {pub use crate::__cargo_equip::macros::chminmax::*;#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_min{($a:expr$(,)*)=>{{$a}};($a:expr,$b:expr$(,)*)=>{{std::cmp::min($a,$b)}};($a:expr,$($rest:expr),+$(,)*)=>{{std::cmp::min($a,$crate::__cargo_equip::crates::chminmax::min!($($rest),+))}};}macro_rules!min{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_min!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_max{($a:expr$(,)*)=>{{$a}};($a:expr,$b:expr$(,)*)=>{{std::cmp::max($a,$b)}};($a:expr,$($rest:expr),+$(,)*)=>{{std::cmp::max($a,$crate::__cargo_equip::crates::chminmax::max!($($rest),+))}};}macro_rules!max{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_max!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_chmin{($base:expr,$($cmps:expr),+$(,)*)=>{{let cmp_min=$crate::__cargo_equip::crates::chminmax::min!($($cmps),+);if$base>cmp_min{$base=cmp_min;true}else{false}}};}macro_rules!chmin{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_chminmax_chmin!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_chminmax_chmax{($base:expr,$($cmps:expr),+$(,)*)=>{{let cmp_max=$crate::__cargo_equip::crates::chminmax::max!($($cmps),+);if$base(crate::__cargo_equip_macro_def_chminmax_chmax!{$($tt)*})}} pub mod __lazy_static_1_4_0 {#![no_std]use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;pub use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;extern crate core;extern crate std;use self::std::prelude::v1::*;use self::std::cell::Cell;use self::std::hint::unreachable_unchecked;use self::std::sync::Once;#[allow(deprecated)]pub use self::std::sync::ONCE_INIT;pub struct Lazy(Cell>,Once);implLazy{#[allow(deprecated)]pub const INIT:Self=Lazy(Cell::new(None),ONCE_INIT);#[inline(always)]pub fn get(&'static self,f:F)->&T where F:FnOnce()->T,{self.1.call_once(||{self.0.set(Some(f()));});unsafe{match*self.0.as_ptr(){Some(ref x)=>x,None=>{debug_assert!(false,"attempted to derefence an uninitialized lazy static. This is a bug");unreachable_unchecked()},}}}}unsafe implSync for Lazy{}#[macro_export]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create{($NAME:ident,$T:ty)=>{static$NAME:$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy<$T> =$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy::INIT;};}macro_rules!__lazy_static_create{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create!{$($tt)*})}}pub use core::ops::Deref as __Deref;#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal{($(#[$attr:meta])*($($vis:tt)*)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!(@MAKE TY,$(#[$attr])*,($($vis)*),$N);__lazy_static_internal!(@TAIL,$N:$T=$e);lazy_static!($($t)*);};(@TAIL,$N:ident:$T:ty=$e:expr)=>{impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::__Deref for$N{type Target=$T;fn deref(&self)->&$T{#[inline(always)]fn __static_ref_initialize()->$T{$e}#[inline(always)]fn __stability()->&'static$T{__lazy_static_create!(LAZY,$T);LAZY.get(__static_ref_initialize)}__stability()}}impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::LazyStatic for$N{fn initialize(lazy:&Self){let _=&**lazy;}}};(@MAKE TY,$(#[$attr:meta])*,($($vis:tt)*),$N:ident)=>{#[allow(missing_copy_implementations)]#[allow(non_camel_case_types)]#[allow(dead_code)]$(#[$attr])*$($vis)*struct$N{__private_field:()}#[doc(hidden)]$($vis)*static$N:$N=$N{__private_field:()};};()=>()}macro_rules!__lazy_static_internal{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static{($(#[$attr:meta])*static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*()static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub)static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub($($vis:tt)+)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub($($vis)+))static ref$N:$T=$e;$($t)*);};()=>()}macro_rules!lazy_static{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static!{$($tt)*})}pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn initialize(lazy:&T){LazyStatic::initialize(lazy);}} pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]use crate::__cargo_equip::preludes::proconio::*;pub use crate::__cargo_equip::macros::proconio::*;pub mod marker{use crate::__cargo_equip::preludes::proconio::*;use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::io::BufRead;pub enum Chars{}impl Readable for Chars{type Output=Vec;fn read>(source:&mut S)->Vec{source.next_token_unwrap().chars().collect()}}pub enum Bytes{}impl Readable for Bytes{type Output=Vec;fn read>(source:&mut S)->Vec{source.next_token_unwrap().bytes().collect()}}pub enum Usize1{}impl Readable for Usize1{type Output=usize;fn read>(source:&mut S)->usize{usize::read(source).checked_sub(1).expect("attempted to read the value 0 as a Usize1")}}pub enum Isize1{}impl Readable for Isize1{type Output=isize;fn read>(source:&mut S)->isize{isize::read(source).checked_sub(1).unwrap_or_else(||{panic!(concat!("attempted to read the value {} as a Isize1:"," the value is isize::MIN and cannot be decremented"),std::isize::MIN,)})}}}pub mod source{use crate::__cargo_equip::preludes::proconio::*;use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;pub mod line{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::str::SplitWhitespace;pub struct LineSource{tokens:Peekable>,current_context:Box,reader:R,}implLineSource{pub fn new(reader:R)->LineSource{LineSource{current_context:"".to_string().into_boxed_str(),tokens:"".split_whitespace().peekable(),reader,}}fn prepare(&mut self){while self.tokens.peek().is_none(){let mut line=String::new();let num_bytes=self.reader.read_line(&mut line).expect("failed to get linel maybe an IO error.");if num_bytes==0{return;}self.current_context=line.into_boxed_str();self.tokens=unsafe{std::mem::transmute::<_,&'static str>(&*self.current_context)}.split_whitespace().peekable();}}}implSourcefor LineSource{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for LineSource>{fn from(s:&'a str)->LineSource>{LineSource::new(BufReader::new(s.as_bytes()))}}}pub mod once{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::marker::PhantomData;use std::str::SplitWhitespace;pub struct OnceSource{tokens:Peekable>,context:Box,_read:PhantomData,}implOnceSource{pub fn new(mut source:R)->OnceSource{let mut context=String::new();source.read_to_string(&mut context).expect("failed to read from source; maybe an IO error.");let context=context.into_boxed_str();let mut res=OnceSource{context,tokens:"".split_whitespace().peekable(),_read:PhantomData,};use std::mem;let context:&'static str=unsafe{mem::transmute(&*res.context)};res.tokens=context.split_whitespace().peekable();res}}implSourcefor OnceSource{fn next_token(&mut self)->Option<&str>{self.tokens.next()}fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for OnceSource>{fn from(s:&'a str)->OnceSource>{OnceSource::new(BufReader::new(s.as_bytes()))}}}pub mod auto{use crate::__cargo_equip::preludes::proconio::*;#[cfg(debug_assertions)]pub use super::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as AutoSource;}pub trait Source{fn next_token(&mut self)->Option<&str>;fn is_empty(&mut self)->bool;fn next_token_unwrap(&mut self)->&str{self.next_token().expect(concat!("failed to get the next token; ","maybe reader reached an end of input. ","ensure that arguments for `input!` macro is correctly ","specified to match the problem input."))}}impl>Sourcefor&'_ mut S{fn next_token(&mut self)->Option<&str>{(*self).next_token()}fn is_empty(&mut self)->bool{(*self).is_empty()}}pub trait Readable{type Output;fn read>(source:&mut S)->Self::Output;}implReadable for T where T::Err:Debug,{type Output=T;fn read>(source:&mut S)->T{let token=source.next_token_unwrap();match token.parse(){Ok(v)=>v,Err(e)=>panic!(concat!("failed to parse the input `{input}` ","to the value of type `{ty}`: {err:?}; ","ensure that the input format is collectly specified ","and that the input value must handle specified type.",),input=token,ty=type_name::(),err=e,),}}}}use crate::__cargo_equip::crates::proconio::source::auto::AutoSource;use lazy_static::lazy_static;use std::io;use std::io::{BufReader,Stdin};use std::sync::Mutex;pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;lazy_static!{#[doc(hidden)]pub static ref STDIN_SOURCE:Mutex>>=Mutex::new(AutoSource::new(BufReader::new(io::stdin())));}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_input{(@from[$source:expr]@rest)=>{};(@from[$source:expr]@rest mut$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[mut]@rest$($rest)*}};(@from[$source:expr]@rest$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@rest$var:tt:$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[$($mut)*]@var$var@kind[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest)=>{let$($mut)*$var=$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*]@rest);$crate::__cargo_equip::crates::proconio::input!(@from[$source]@rest$($rest)*);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*$tt]@rest$($rest)*);};(from$source:expr,$($rest:tt)*)=>{#[allow(unused_variables,unused_mut)]let mut s=$source;$crate::__cargo_equip::crates::proconio::input!{@from[&mut s]@rest$($rest)*}};($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","."));$crate::__cargo_equip::crates::proconio::input!{@from[&mut*locked_stdin]@rest$($rest)*}drop(locked_stdin);};}macro_rules!input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_input!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_read_value{(@source[$source:expr]@kind[[$($kind:tt)*]])=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[]@rest$($kind)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest)=>{{let len=::read($source);$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[[$($kind)*;len]])}};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest;$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*]@len[$($rest)*])};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*$tt]@rest$($rest)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@len[$($len:tt)*])=>{{let len=$($len)*;(0..len).map(|_|$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*])).collect::>()}};(@source[$source:expr]@kind[($($kinds:tt)*)])=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[]@current[]@rest$($kinds)*)};(@tuple@source[$source:expr]@kinds[$([$($kind:tt)*])*]@current[]@rest)=>{($($crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]),)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest$($rest)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*]@current[$($curr)*$tt]@rest$($rest)*)};(@source[$source:expr]@kind[])=>{compile_error!(concat!("Reached unreachable statement while parsing macro input. ","This is a bug in `proconio`. ","Please report this issue from ","."));};(@source[$source:expr]@kind[$kind:ty])=>{<$kind as$crate::__cargo_equip::crates::proconio::__Readable>::read($source)}}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_read_value!{$($tt)*})}pub fn is_stdin_empty()->bool{use crate::__cargo_equip::crates::proconio::source::Source;let mut lock=STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program. ","If this issue repeatedly occur, this is a bug in `proconio`. ","Please report this issue from ","."));lock.is_empty()}} pub mod segment_tree {use crate::__cargo_equip::preludes::segment_tree::*;use std::ops::{Bound,RangeBounds};use algebraic::Monoid;#[derive(Clone)]pub struct SegmentTreewhere M:Monoid,M::S:Clone,{n:usize,v:Vec,}implSegmentTreewhere M:Monoid,M::S:Clone,{pub fn new(n:usize)->Self{Self{n,v:vec![M::e();n*2],}}pub fn set(&mut self,mut k:usize,x:M::S){k+=self.n;self.v[k]=x;while k>1{k>>=1;self.v[k]=M::op(&self.v[k*2],&self.v[k*2+1]);}}pub fn get(&self,k:usize)->M::S{assert!(k(&self,range:R)->M::S where R:RangeBounds,{let mut l=match range.start_bound(){Bound::Excluded(&l)=>l+1,Bound::Included(&l)=>l,Bound::Unbounded=>0,};let mut r=match range.end_bound(){Bound::Excluded(&r)=>r,Bound::Included(&r)=>r+1,Bound::Unbounded=>self.n,};assert!(l<=r);assert!(r<=self.n);l+=self.n;r+=self.n;let mut sl=M::e();let mut sr=M::e();while l>=1;r>>=1;}M::op(&sl,&sr)}pub fn max_right

(&self,mut l:usize,pred:P)->usize where P:Fn(&M::S)->bool,{assert!(l<=self.n);assert!(pred(&M::e()));if pred(&self.prod(l..)){return self.n;}l+=self.n;let mut s=M::e();loop{while l&1==0&&self.is_good_node(l>>1){l>>=1;}if!pred(&M::op(&s,&self.v[l])){while l(&self,mut r:usize,pred:P)->usize where P:Fn(&M::S)->bool,{assert!(r<=self.n);assert!(pred(&M::e()));if pred(&self.prod(..r)){return 0;}r+=self.n;let mut s=M::e();loop{r-=1;while!self.is_good_node(r){r=r*2+1;}while r&1!=0&&self.is_good_node(r>>1){r>>=1;}if!pred(&M::op(&self.v[r],&s)){while rbool{if k>=self.n{true}else{let d=k.leading_zeros()-self.n.leading_zeros();self.n>>d!=k||self.n>>d<From>for SegmentTreewhere M:Monoid,M::S:Clone,{fn from(mut a:Vec)->Self{let n=a.len();let mut v=vec![M::e();n];v.append(&mut a);for i in(1..n).rev(){v[i]=M::op(&v[i*2],&v[i*2+1]);}Self{n,v}}}} pub mod sliding_window_aggregation {use crate::__cargo_equip::preludes::sliding_window_aggregation::*;use algebraic::Monoid;pub struct SlidingWindowAggregationwhere M:Monoid,M::S:Clone,{fv:Vec,bv:Vec,fs:Vec,bs:Vec,}implSlidingWindowAggregationwhere M:Monoid,M::S:Clone,{pub fn new()->Self{Self{fv:vec![],bv:vec![],fs:vec![M::e()],bs:vec![M::e()],}}pub fn clear(&mut self){self.fv.clear();self.bv.clear();self.fs.clear();self.fs.push(M::e());self.bs.clear();self.bs.push(M::e());}pub fn len(&self)->usize{self.fv.len()+self.bv.len()}pub fn is_empty(&self)->bool{self.len()==0}pub fn push_back(&mut self,x:M::S){self.bs.push(M::op(self.bs.last().unwrap(),&x));self.bv.push(x);}pub fn push_front(&mut self,x:M::S){self.fs.push(M::op(&x,self.fs.last().unwrap()));self.fv.push(x);}pub fn pop_back(&mut self)->Option{if self.len()==0{None}else if self.len()==1{if self.bv.len()==1{self.bs.pop();self.bv.pop()}else{self.fs.pop();self.fv.pop()}}else{if self.bv.is_empty(){self.rebuild();}self.bs.pop();self.bv.pop()}}pub fn pop_front(&mut self)->Option{if self.len()==0{None}else if self.len()==1{if self.bv.len()==1{self.bs.pop();self.bv.pop()}else{self.fs.pop();self.fv.pop()}}else{if self.fv.is_empty(){self.rebuild();}self.fs.pop();self.fv.pop()}}pub fn prod(&self)->M::S{M::op(self.fs.last().unwrap(),self.bs.last().unwrap())}fn rebuild(&mut self){let mut v=vec![];v.reserve(self.len());v.append(&mut self.fv);v.reverse();v.append(&mut self.bv);self.clear();for x in v[0..v.len()/2].iter().rev(){self.push_front(x.clone());}for x in&v[v.len()/2..v.len()]{self.push_back(x.clone());}}}} } pub(crate) mod macros { pub mod algebraic {pub use crate::{__cargo_equip_macro_def_algebraic_act as act,__cargo_equip_macro_def_algebraic_algebra as algebra,__cargo_equip_macro_def_algebraic_group as group,__cargo_equip_macro_def_algebraic_monoid as monoid};} pub mod chminmax {pub use crate::{__cargo_equip_macro_def_chminmax_chmax as chmax,__cargo_equip_macro_def_chminmax_chmin as chmin,__cargo_equip_macro_def_chminmax_max as max,__cargo_equip_macro_def_chminmax_min as min};} pub mod __lazy_static_1_4_0 {pub use crate::{__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create as __lazy_static_create,__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal as __lazy_static_internal,__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static as lazy_static};} pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_read_value as read_value};} pub mod segment_tree {} pub mod sliding_window_aggregation {} } pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::__lazy_static_1_4_0::*};} mod preludes { pub mod algebraic {} pub mod chminmax {} pub mod __lazy_static_1_4_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;} pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__lazy_static_1_4_0 as lazy_static;} pub mod segment_tree {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebraic;} pub mod sliding_window_aggregation {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::algebraic;} } }