Рон — счастливый обладатель перестановки \(a\) длины \(n\).
Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) — не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Над перестановкой Рона ставится \(m\) экспериментов следующего вида: (\(r_i\), \(p_i\)). Это обозначает, что элементы в диапазоне \([1, r_i]\) (другими словами, префикс длины \(r_i\)) будут отсортированы в возрастающем порядке с вероятностью \(p_i\). Все эксперименты проводятся в том же порядке, в котором задаются во входных данных.
Для примера рассмотрим перестановку \([4, 2, 1, 5, 3]\) и эксперимент (\(3, 0.6\)). После такого эксперимента с вероятностью \(60\%\) перестановка примет вид \([1, 2, 4, 5, 3]\), а с вероятностью \(40\%\) останется без изменений.
Вам требуется определить, с какой вероятностью перестановка станет полностью отсортированной по возрастанию после \(m\) экспериментов.
Выходные данные
Для каждого набора входных данных выведите единственное число — вероятность, что после всех экспериментов перестановка окажется отсортированной. Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит \(10^{-6}\).
Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если и только если \(\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}\).
Примечание
Для первого набора входных данных можно показать, что только от того, выполнится ли сортировка с помощью правила \((4, 0.6)\), зависит, будет ли итоговая перестановка отсортированной.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 3
4 3 2 1
1 0.3
3 1
4 0.6
5 3
4 2 1 3 5
3 0.8
4 0.6
5 0.3
6 5
1 3 2 4 5 6
4 0.9
5 0.3
2 0.4
6 0.7
3 0.5
4 2
1 2 3 4
2 0.5
4 0.1
|
0.600000
0.720000
0.989500
1.000000
|