use std::collections::*;
use std::io::BufRead;
use std::str::FromStr;
fn count_rounds(list: &[usize]) -> usize {
let mut res = 0;
let mut seen = vec![false; list.len()];
for v in list {
if *v == 1 || !seen[v - 2] {
res += 1;
}
seen[v - 1] = true;
}
return res;
}
fn solve_brute(list: Vec<usize>) -> (usize, usize) {
let mut list = list;
let mut counts = BTreeMap::<usize, usize>::new();
for a in 0..list.len() {
for b in a + 1..list.len() {
list.swap(a, b);
counts
.entry(count_rounds(&list))
.and_modify(|v| *v += 1)
.or_insert(1);
list.swap(a, b);
}
}
counts.into_iter().next().unwrap()
}
#[derive(Clone)]
struct SegTree {
tree: Vec<isize>,
}
impl SegTree {
fn new(n: usize) -> Self {
assert!(n < usize::MAX / 2);
// TODO: Check that n is power of 2
Self {
tree: vec![0; 2 * n],
}
}
fn add(&mut self, i: usize, val: isize) {
let mut i = i + self.tree.len() / 2;
while i > 0 {
self.tree[i] += val;
i /= 2;
}
}
fn get(&self, l: usize, r: usize) -> isize {
let mut l = l + self.tree.len() / 2;
let mut r = r + self.tree.len() / 2;
let mut res = 0;
while l < r {
if l % 2 == 1 {
res += self.tree[l];
l += 1;
}
if r % 2 == 0 {
res += self.tree[r];
r -= 1;
}
l /= 2;
r /= 2;
}
if l == r {
res += self.tree[l];
}
res
}
}
#[derive(Debug, PartialOrd, Ord, PartialEq, Eq)]
struct Event {
position: usize,
target: usize,
list: i8,
amount: isize,
}
#[derive(Debug)]
struct Ranges {
target: usize,
left: usize,
right: usize,
outer: i8,
inner: i8,
}
impl Into<Vec<Event>> for Ranges {
fn into(self) -> Vec<Event> {
vec![
Event {
target: self.target,
position: 0,
list: self.outer,
amount: 1,
},
Event {
target: self.target,
position: self.left,
list: self.outer,
amount: -1,
},
Event {
target: self.target,
position: self.left,
list: self.inner,
amount: 1,
},
Event {
target: self.target,
position: self.right,
list: self.inner,
amount: -1,
},
Event {
target: self.target,
position: self.right,
list: self.outer,
amount: 1,
},
]
}
}
fn ranges(indices: &[usize], p: usize) -> Ranges {
let i = indices[p];
if p == 1 {
let nexti = *indices.get(p + 1).unwrap_or(&indices.len());
return if i < nexti {
// 1 2
Ranges {
target: i,
left: 0,
right: nexti + 1,
outer: 1,
inner: 0,
}
} else {
// 2 1
Ranges {
target: i,
left: 0,
right: nexti + 1,
outer: 0,
inner: -1,
}
};
}
let previ = indices[p - 1];
let nexti = *indices.get(p + 1).unwrap_or(&indices.len());
if previ < nexti {
let (outer, inner) = if i < previ {
// i pi ni
(0, -1)
} else if i < nexti {
// pi i ni
(1, 0)
} else {
// pi ni i
(0, -1)
};
Ranges {
target: i,
left: previ + 1,
right: nexti + 1,
outer,
inner,
}
} else {
let (outer, inner) = if i < nexti {
// i ni pi
(0, 1)
} else if i < previ {
// ni i pi
(-1, 0)
} else {
// ni pi i
(0, 1)
};
Ranges {
target: i,
left: nexti + 1,
right: previ + 1,
outer,
inner,
}
}
}
fn events(perm: &[usize], indices: &[usize]) -> Vec<Event> {
let mut events = Vec::new();
for p in 1..=perm.len() {
let ev: Vec<_> = ranges(indices, p).into();
events.extend(ev.into_iter());
// if previ < nexti {
// if i < previ {
// // i pi ni
// events.push(Event {
// position: 0,
// list: 0,
// amount: 1,
// });
// events.push(Event {
// position: previ + 1,
// list: 0,
// amount: -1,
// });
// events.push(Event {
// position: previ + 1,
// list: -1,
// amount: 1,
// });
// events.push(Event {
// position: nexti + 1,
// list: -1,
// amount: -1,
// });
// events.push(Event {
// position: nexti + 1,
// list: 0,
// amount: 1,
// });
// } else if i < nexti {
// // pi i ni
// events.push(Event {
// position: 0,
// list: 1,
// amount: 1,
// });
// events.push(Event {
// position: previ + 1,
// list: 1,
// amount: -1,
// });
// events.push(Event {
// position: previ + 1,
// list: 0,
// amount: 1,
// });
// events.push(Event {
// position: nexti + 1,
// list: 0,
// amount: -1,
// });
// events.push(Event {
// position: nexti + 1,
// list: 1,
// amount: 1,
// });
// } else {
// // pi ni i
// events.push(Event {
// position: 0,
// list: 0,
// amount: 1,
// });
// events.push(Event {
// position: previ + 1,
// list: 0,
// amount: -1,
// });
// events.push(Event {
// position: previ + 1,
// list: -1,
// amount: 1,
// });
// events.push(Event {
// position: nexti + 1,
// list: -1,
// amount: -1,
// });
// events.push(Event {
// position: nexti + 1,
// list: 0,
// amount: 1,
// });
// }
// } else {
// if i < nexti {
// // i ni pi
// events.push(Event {
// position: 0,
// list: 0,
// amount: 1,
// });
// events.push(Event {
// position: nexti + 1,
// list: 0,
// amount: -1,
// });
// events.push(Event {
// position: nexti + 1,
// list: 1,
// amount: 1,
// });
// events.push(Event {
// position: previ + 1,
// list: 1,
// amount: -1,
// });
// events.push(Event {
// position: previ + 1,
// list: 0,
// amount: 1,
// });
// } else if i < previ {
// // ni i pi
// events.push(Event {
// position: 0,
// list: -1,
// amount: 1,
// });
// events.push(Event {
// position: nexti + 1,
// list: -1,
// amount: -1,
// });
// events.push(Event {
// position: nexti + 1,
// list: 0,
// amount: 1,
// });
// events.push(Event {
// position: previ + 1,
// list: 0,
// amount: -1,
// });
// events.push(Event {
// position: previ + 1,
// list: -1,
// amount: 1,
// });
// } else {
// // ni pi i
// events.push(Event {
// position: 0,
// list: 0,
// amount: 1,
// });
// events.push(Event {
// position: nexti + 1,
// list: 0,
// amount: -1,
// });
// events.push(Event {
// position: nexti + 1,
// list: 1,
// amount: 1,
// });
// events.push(Event {
// position: previ + 1,
// list: 1,
// amount: -1,
// });
// events.push(Event {
// position: previ + 1,
// list: 0,
// amount: 1,
// });
// }
// }
}
events
}
fn solve(perm: Vec<usize>) -> (usize, usize) {
let mut indices = vec![0; perm.len() + 1];
for (i, p) in perm.iter().enumerate() {
indices[*p] = i;
}
let base_score = count_rounds(&perm);
let mut events = events(&perm, &indices);
events.sort();
const N: usize = 1 << 20;
let mut trees = [SegTree::new(N), SegTree::new(N), SegTree::new(N)];
let mut counts = [0; 5];
let mut events = events.into_iter().peekable();
for (i, p) in perm.into_iter().enumerate() {
// println!("i = {}, p = {}", i, p);
// Update trees based on events
while events
.peek()
.and_then(|e| Some(e.position <= i))
.unwrap_or(false)
{
let event = events.next().unwrap();
trees[(event.list + 1) as usize].add(event.target, event.amount);
// println!("Event: {:?}", event);
}
// Compute overlapping ranges
let ranges = ranges(&indices, p);
// println!("Range: {:?}", ranges);
for (i, tree) in trees.iter().enumerate() {
if ranges.left > 0 {
// println!(
// "counts[{} + {}] += {}",
// i as isize - 1,
// ranges.outer as isize,
// tree.get(0, ranges.left - 1)
// );
counts[i + (ranges.outer + 1) as usize] += tree.get(0, ranges.left - 1);
}
// println!(
// "counts[{} + {}] += {}",
// i as isize - 1,
// ranges.inner as isize,
// tree.get(ranges.left, ranges.right - 1)
// );
counts[i + (ranges.inner + 1) as usize] += tree.get(ranges.left, ranges.right - 1);
// println!(
// "counts[{} + {}] += {}",
// i as isize - 1,
// ranges.outer as isize,
// tree.get(ranges.right, indices.len() + 2)
// );
counts[i + (ranges.outer + 1) as usize] += tree.get(ranges.right, indices.len() + 2);
}
// Remove self-effect
if ranges.left <= i && i < ranges.right {
// println!("Removing inner counts[{}, {}]", ranges.inner, ranges.inner);
counts[(2 * ranges.inner + 2) as usize] -= 1;
} else {
// println!("Removing outer counts[{}, {}]", ranges.outer, ranges.outer);
counts[(2 * ranges.outer + 2) as usize] -= 1;
}
}
// println!("Base score: {}", base_score);
// println!("{:?}", counts);
for (i, c) in counts.iter().enumerate() {
if *c > 0 {
return (base_score + i - 2, *c as usize / 2);
}
}
// solve_brute(perm)
unreachable!();
}
fn main() {
let stdin = std::io::stdin();
let stdin = stdin.lock();
let mut lines = stdin.lines();
let n = usize::from_str(&lines.next().unwrap().unwrap()).unwrap();
let list: Vec<_> = lines
.next()
.unwrap()
.unwrap()
.split_whitespace()
.map(|v| usize::from_str(&v).unwrap())
.collect();
assert_eq!(list.len(), n);
let (minimum, possibilities) = solve(list);
println!("{} {}", minimum, possibilities);
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_count_rounds() {
assert_eq!(count_rounds(&[1, 2, 3, 4]), 1);
assert_eq!(count_rounds(&[4, 3, 2, 1]), 4);
assert_eq!(count_rounds(&[6, 1, 4, 5, 7, 3, 8, 2]), 4);
assert_eq!(count_rounds(&[6, 3, 4, 5, 7, 1, 8, 2]), 3);
}
#[test]
fn test_brute_solver() {
assert_eq!(solve_brute(vec![6, 1, 4, 5, 7, 3, 8, 2]), (3, 5));
}
struct Permutations {
state: Option<Vec<usize>>,
}
impl Permutations {
fn new(n: usize) -> Self {
Self {
state: Some((1..=n).collect()),
}
}
}
impl std::iter::Iterator for Permutations {
type Item = Vec<usize>;
fn next(&mut self) -> Option<Self::Item> {
let state = match &mut self.state {
Some(res) => res,
None => return None,
};
let res = state.clone();
// Compute next permutation
let mut i = state.len() - 1;
loop {
let i1 = i;
i -= 1;
if state[i] < state[i1] {
let mut i2 = state.len() - 1;
while !(state[i] < state[i2]) {
i2 -= 1;
}
state.swap(i, i2);
state[i1..].reverse();
return Some(res);
}
if i == 0 {
self.state = None;
return Some(res);
}
}
}
}
#[test]
fn test_against_brute_2() {
for perm in Permutations::new(2) {
assert_eq!(
solve(perm.clone()),
solve_brute(perm.clone()),
"Input {:?}",
perm
);
}
}
#[test]
fn test_against_brute_3() {
for perm in Permutations::new(3) {
assert_eq!(
solve(perm.clone()),
solve_brute(perm.clone()),
"Input {:?}",
perm
);
}
}
#[test]
fn test_against_brute_4() {
for perm in Permutations::new(4) {
assert_eq!(
solve(perm.clone()),
solve_brute(perm.clone()),
"Input {:?}",
perm
);
}
}
#[test]
fn test_against_brute_5() {
for perm in Permutations::new(5) {
assert_eq!(
solve(perm.clone()),
solve_brute(perm.clone()),
"Input {:?}",
perm
);
}
}
#[test]
fn test_against_brute_6() {
for perm in Permutations::new(6) {
assert_eq!(
solve(perm.clone()),
solve_brute(perm.clone()),
"Input {:?}",
perm
);
}
}
#[test]
fn test_against_brute_7() {
for perm in Permutations::new(7) {
assert_eq!(
solve(perm.clone()),
solve_brute(perm.clone()),
"Input {:?}",
perm
);
}
}
#[test]
fn test_speed_200000() {
use rand::distributions::{Distribution, Uniform};
use std::time::{Duration, Instant};
const ITERS: u32 = 30;
const SIZE: usize = 200000;
let mut time = Duration::from_nanos(1);
for i in 0..ITERS {
let mut input: Vec<usize> = (1..=SIZE).collect();
for i in 0..SIZE {
input.swap(i, Uniform::from(i..SIZE).sample(&mut rand::thread_rng()));
}
std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
let start = Instant::now();
std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
solve(input);
std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
let stop = Instant::now();
std::sync::atomic::fence(std::sync::atomic::Ordering::AcqRel);
time += stop - start;
}
let time = (time / ITERS).as_secs_f64();
assert!(time < 1.0, "Took time {}", time);
}
fn print_outer(left: usize, right: usize, width: usize) {
assert!(left < right);
let right = right.min(width);
// Left part of the range
if left > 0 {
print!("├─{}┤ ", "─".repeat(2 * (left - 1)));
} else {
print!(" ");
}
if right < width {
// Middle part
print!("{}", " ".repeat(2 * (right - left - 1)));
// Right part
print!("├─{}┤", "─".repeat(2 * (width - right - 1)));
}
}
fn print_inner(left: usize, right: usize, width: usize) {
assert!(left < right);
let right = right.min(width);
// Padding
print!("{}", " ".repeat(2 * (left)));
// Bar
print!("├─{}┤ ", "─".repeat(2 * (right - left - 1)));
}
fn print_ranges(perm: Vec<usize>) {
let mut indices = vec![0; perm.len() + 1];
for (i, p) in perm.iter().enumerate() {
indices[*p] = i;
}
println!(
" {}",
perm.iter()
.map(|p| p.to_string())
.collect::<Vec<_>>()
.join(" ")
);
for p in 1..=perm.len() {
let i = indices[p];
// Print p at correct position
println!(" {}{}", " ".repeat(2 * i), p);
let ranges = ranges(&indices, p);
// println!("{:?}", ranges);
let mut prints: [Option<fn(usize, usize, usize)>; 3] = [None, None, None];
prints[(ranges.inner + 1) as usize] = Some(print_inner);
prints[(ranges.outer + 1) as usize] = Some(print_outer);
print!("-1 ");
prints[0].and_then(|f| Some(f(ranges.left, ranges.right, perm.len())));
println!();
print!(" 0 ");
prints[1].and_then(|f| Some(f(ranges.left, ranges.right, perm.len())));
println!();
print!("+1 ");
prints[2].and_then(|f| Some(f(ranges.left, ranges.right, perm.len())));
println!();
}
}
// #[test]
// fn foo() {
// // ranges(vec![1, 2, 3]);
// // solve(vec![1, 2, 3]);
// // print_ranges(vec![2, 3, 1]);
// // solve(vec![2, 3, 1]);
// // ranges(vec![6, 1, 4, 5, 7, 3, 8, 2]);
// // solve(vec![6, 1, 4, 5, 7, 3, 8, 2]);
// // ranges(vec![2, 1, 3]);
// // ranges(vec![1, 2, 3, 4, 5]);
// // ranges(vec![1, 3, 2]);
// // ranges(vec![2, 3, 1, 4]);
// // ranges(vec![3, 1, 2, 4]);
// for perm in Permutations::new(4) {
// // let start = count_rounds(&perm);
// // let best = solve_brute(perm.clone()).0;
// // println!("{:?}", perm);
// // ranges(perm);
// // assert!(best != start, "Input {:?}, {}, {}", perm, best, start);
// // assert_eq!(
// // solve(perm.clone()),
// // solve_brute(perm.clone()),
// // "Input {:?}",
// // perm
// // );
// }
// // assert!(false);
// }
}
