#![allow(unused_macros)] #![allow(dead_code)] #![allow(unused_imports)] // # ファイル構成 // - use 宣言 // - lib モジュール // - main 関数 // - basic モジュール // // 常に使うテンプレートライブラリは basic モジュール内にあります。 // 問題に応じて使うライブラリ lib モジュール内にコピペしています。 // ライブラリのコードはこちら → https://github.com/RheoTommy/at_coder // Twitter はこちら → https://twitter.com/RheoTommy use std::collections::*; use std::io::{stdout, BufWriter, Write}; use crate::basic::*; use crate::lib::*; pub mod lib { pub trait LazyMonoid { type M: Clone; type L: Clone; fn e() -> Self::M; fn id() -> Self::L; } pub struct LazySegTree { n: usize, height: usize, len: usize, data: Vec<(M::M, M::L)>, fold: Box M::M>, eval: Box M::M>, merge: Box M::L>, } impl std::fmt::Debug for LazySegTree where ::M: std::fmt::Debug, ::L: std::fmt::Debug, { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { for i in 0..=self.height { for j in 0..1 << i { write!(f, "{:?} ", &self.data[(1 << i) + j])?; } writeln!(f)?; } write!(f, "") } } impl LazySegTree { pub fn new( n: usize, fold: Box M::M>, eval: Box M::M>, merge: Box M::L>, ) -> Self { let len = n; let n = n.next_power_of_two(); let height = n.trailing_zeros() as usize; Self { n, height, len, fold, eval, merge, data: vec![(M::e(), M::id()); 2 * n], } } pub fn from_slice( a: &[M::M], mut fold: Box M::M>, eval: Box M::M>, merge: Box M::L>, ) -> Self { let n = a.len().next_power_of_two(); let height = n.trailing_zeros() as usize; let mut data = vec![(M::e(), M::id()); 2 * n]; for i in 0..a.len() { data[i + n].0 = a[i].clone(); } for i in (1..n).rev() { data[i].0 = fold(&data[i * 2].0, &data[i * 2 + 1].0); } Self { n, height, len: a.len(), data, fold, eval, merge, } } fn apply(&mut self, x: usize, op: &M::L) { let node = &mut self.data[x]; node.0 = (self.eval)(&node.0, op); node.1 = (self.merge)(&node.1, op); } fn propagate_at(&mut self, x: usize) { let op = std::mem::replace(&mut self.data[x].1, M::id()); self.apply(2 * x, &op); self.apply(2 * x + 1, &op); } fn save_at(&mut self, x: usize) { self.data[x].0 = (self.fold)(&self.data[x * 2].0, &self.data[x * 2 + 1].0); } fn propagate(&mut self, l: usize, r: usize) { let l = l + self.n; let r = r + self.n; for i in (1..=self.height).rev() { if (l >> i) << i != l { self.propagate_at(l >> i); } if (r >> i) << i != r { self.propagate_at((r - 1) >> i); } } } fn save(&mut self, l: usize, r: usize) { let l = l + self.n; let r = r + self.n; for i in 1..=self.height { if (l >> i) << i != l { self.save_at(l >> i); } if (r >> i) << i != r { self.save_at((r - 1) >> i); } } } pub fn set(&mut self, l: usize, r: usize, op: M::L) { assert!(l <= r && r <= self.n); if l == r { return; } self.propagate(l, r); let mut x = l + self.n; let mut y = r + self.n; while x < y { if x & 1 == 1 { self.apply(x, &op); x += 1; } if y & 1 == 1 { y -= 1; self.apply(y, &op); } x >>= 1; y >>= 1; } self.save(l, r) } pub fn fold(&mut self, l: usize, r: usize) -> M::M { assert!(l <= r && r <= self.n); if l == r { return M::e(); } self.propagate(l, r); let mut x = l + self.n; let mut y = r + self.n; let mut p = M::e(); let mut q = M::e(); while x < y { if x & 1 == 1 { p = (self.fold)(&p, &self.data[x].0); x += 1; } if y & 1 == 1 { y -= 1; q = (self.fold)(&self.data[y].0, &q); } x >>= 1; y >>= 1; } (self.fold)(&p, &q) } pub fn find_rightest(&mut self, l: usize, mut p: impl FnMut(&M::M) -> bool) -> usize { assert!(l < self.n); self.propagate(l, self.n); if p(&self.fold(l, self.n)) { return self.len; } let mut now = M::e(); let mut res = l + self.n; while res + 1 != res.next_power_of_two() { if res & 1 == 1 { let tmp = (self.fold)(&now, &self.data[res].0); if !p(&tmp) { break; } now = tmp; res += 1; } res >>= 1; } while res < self.n { res <<= 1; let tmp = (self.fold)(&now, &self.data[res].0); if p(&tmp) { now = tmp; res += 1; } } (res - self.n).min(self.len) } pub fn find_leftest(&mut self, r: usize, mut p: impl FnMut(&M::M) -> bool) -> usize { assert!(r <= self.n); self.propagate(0, r); if p(&self.fold(0, r)) { return 0; } let mut now = M::e(); let mut res = r + self.n; while res > 1 { if res & 1 == 1 { res -= 1; let tmp = (self.fold)(&self.data[res].0, &now); if !p(&tmp) { break; } now = tmp; } res >>= 1; } while res < self.n { res <<= 1; res += 1; let tmp = (self.fold)(&self.data[res].0, &now); if p(&tmp) { res -= 1; now = tmp; } } (res - self.n + 1).min(self.len) } } } struct M; impl LazyMonoid for M { type M = (usize, usize); type L = Option<(usize, usize)>; fn e() -> Self::M { (0, 0) } fn id() -> Self::L { None } } fn main() { let mut io = IO::new(); let n = io.next_usize(); let a = io.next_vec::(n); let mut lst = LazySegTree::::new( n + 2, Box::new(|a, b| (a.0 + b.0, a.1 + b.1)), Box::new(|a, b| if b.is_none() { *a } else { b.unwrap() }), Box::new(|a, b| match (a, b) { (_, Some(b)) => Some(*b), (a, _) => *a, }), ); assert!(n <= 100000); for &ai in &a { assert!(ai <= n); } let mut index = vec![vec![n]; n + 1]; index[0] = (0..=n).collect::>(); for i in 0..n { index[a[i]].push(i); } index.iter_mut().for_each(|vi| { vi.sort(); vi.reverse(); }); let mut max = vec![0; n + 1]; for i in 0..=n { max[i] = *index[i].last().unwrap(); } for i in 0..n { max[i + 1] = (max[i + 1]).max(max[i]); } for ai in 0..=n { let i = max[ai]; let (cnt, sum) = lst.fold(i, i + 1); lst.set(i, i + 1, Some((cnt + 1, sum + i))); } let mut ans = 0; for l in 0..n { ans += n * (n + 1) - lst.fold(0, n + 2).1; println!("{}", lst.fold(0, n + 2).1); let ai = a[l]; let now = lst.find_rightest(0, |(cnt, _)| *cnt < ai); let r = lst.fold(0, now + 1).0; let len = r - ai; let (cnt, sum) = lst.fold(now, now + 1); lst.set(now, now + 1, Some((cnt - len, sum - len * now))); index[ai].pop(); let next = *index[ai].last().unwrap().max(&now); let amount = lst.fold((now + 1).min(next), next).0; lst.set((now + 1).min(next), next, Some((0, 0))); let (cnt, sum) = lst.fold(next, next + 1); lst.set(next, next + 1, Some((cnt + amount + len, sum + next * (len + amount)))); lst.set(l, l + 1, Some((0, 0))); let (cnt, sum) = lst.fold(l + 1, l + 2); lst.set(l + 1, l + 2, Some((cnt + 1, sum + l + 1))); } io.println(ans); } pub mod basic { pub const U_INF: u64 = (1 << 60) + (1 << 30); pub const I_INF: i64 = (1 << 60) + (1 << 30); pub struct IO { iter: std::str::SplitAsciiWhitespace<'static>, buf: std::io::BufWriter>, } impl Default for IO { fn default() -> Self { Self::new() } } impl IO { pub fn new() -> Self { use std::io::*; let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); let input = Box::leak(input.into_boxed_str()); let out = Box::new(stdout()); IO { iter: input.split_ascii_whitespace(), buf: BufWriter::new(Box::leak(out).lock()), } } pub fn next_str(&mut self) -> &str { self.iter.next().unwrap() } pub fn read(&mut self) -> T where ::Err: std::fmt::Debug, { self.iter.next().unwrap().parse().unwrap() } pub fn next_usize(&mut self) -> usize { self.read() } pub fn next_uint(&mut self) -> u64 { self.read() } pub fn next_int(&mut self) -> i64 { self.read() } pub fn next_float(&mut self) -> f64 { self.read() } pub fn next_chars(&mut self) -> std::str::Chars { self.next_str().chars() } pub fn next_vec(&mut self, n: usize) -> Vec where ::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect::>() } pub fn print(&mut self, t: T) { use std::io::Write; write!(self.buf, "{}", t).unwrap(); } pub fn println(&mut self, t: T) { self.print(t); self.print("\n"); } pub fn print_iter>( &mut self, mut iter: I, sep: &str, ) { if let Some(v) = iter.next() { self.print(v); for vi in iter { self.print(sep); self.print(vi); } } self.print("\n"); } pub fn flush(&mut self) { use std::io::Write; self.buf.flush().unwrap(); } } }