Жэфф Фюрик хоёр найзууд бололцсон ба тун зугаатай тоглоом тоглож байна.

Эхэнд Жэфф цаасан дээр $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}$-с хэтрэхгүй бол хариу зөвд тооцогдоно.

In the first test the sequence is already sorted, so the answer is $0$.