Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Жэфф Фюрик хоёр
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Жэфф Фюрик хоёр найзууд бололцсон ба тун зугаатай тоглоом тоглож байна.
Эхэнд Жэфф цаасан дээр $n$ ширхэг ялгаатай тооны сэлгэмэл $p_1,...,p_n$ бичнэ. Тэгээд залуус үйлдлээ хийцгээж эхэлнэ. Жэфф эхний үйлдлийг хийх ба тэр өөрийн үйлдэл дээр сэлгэмлийн дурын хоёр элементийн байрыг солино. Фюрик өөрийн ээлжин дээр зоос хаяад "сүлд" буувал $p_i>p_{i+1}$ байх ямар нэг $i,(i+1)$ индекүүдтэй хөрш элементүүдийг сонгоод байрыг нь солино. Харин "тоо буувал" $p_i Жэфф тоглоомыг аль болох түргэн дуусгахыг хүсч буй. Өөрөөр хэлбэл цөөн үйлдлээр дуусгахыг хүсч байгаа. Жэфф-д тусалж тэр хамгийн боломжит хамгийн сайн хувилбараар тоглоход математикийн хувьд хамгийн цөөндөө тоглоом хэдэн нүүдлийн дараа дуусна гэж найдаж болохыг ол.(математик горьдлогын утга) Зоосны сүлд ба тоогоор тусах магадлал аль аль нь тавин хувь. Эхний мөрөнд $n (1\le n\le 3000)$ бүхэл тоо өгөгдөнө. Удаах мөрөнд $n$ ширхэг ялгаатай бүхэл тоонууд $p_1, p_2, ..., p_n (1\le p_i\le n)$ ($p$ сэлгэмэл) зайгаар тусгаарлаган өгөгдөнө. Бодлогын хариу болох бодит тоог хэвлэнэ үү. Нарийвчлалын алдаа $ 10^{-6}$-с хэтрэхгүй бол хариу зөвд тооцогдоно.Оролт
Гаралт
Орчуулсан: Төрбат
Жишээ тэстүүд
Оролт
2 1 2
Гаралт
0.000000
Оролт
5 3 5 2 4 1
Гаралт
13.000000
Тэмдэглэл
In the first test the sequence is already sorted, so the answer is $0$.