D. Жэфф Фюрик хоёр

хугацааны хязгаарлалт 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$.

Сэтгэгдлүүдийг ачааллаж байна...