E. Сережа ба Хуваалт

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$a_1,a_2,...,a_{|a|}$ бодит тоон дараалал ба $x$ бодит тоон хувьсагч өгөгджээ. Доорх үйлдлийг энэ дараалал дээр хийж болно.

  1. Дарааллын ямар нэг элементийн дугаар $i (1\le i\le |a|)$-г сонго.
  2. Дараах хувиргалтуудыг дэс дарааллуулан гүйцэтгэ: $ tmp =\frac{a_i+x}{2}, a_i=tmp, x=tmp$. $a$ дараалал болон өгөгдсөн үйлдлийг дурын удаа ашиглахад $x$ тооны авах хамгийн их утгыг $g(a,x)$ гэе.

Сережад $ b_1,b_2,...,b_{|b|}$ дараалал өгөгдсөн ба түүнд дараах нийлбэрийг тооцоолоход нь тусална уу: $\sum_{i=1}^{|b|} \sum_{j=i}^{|b|} g([b_i, b_{i + 1}, ..., b_j],0)$.

$[b_i, b_{i + 1}, ..., b_j]$ энэ нь хаалтан дахь элементүүд өгөгдсөн дарааллаараа үүсгэх дарааллыг илтгэнэ. Нарийвчлалын алдаанаас сэргийлж гарсан утгыг $|b|^2$ тоонд хувааж хэвлэнэ үү.

Оролт

Эхний мөрөнд $b$ дарааллын уртыг илэрхийлэх $|b| (1\le |b|\le 3·10^5)$ тоо өгөгдөнө. 2 дахь мөрөнд $|b|$ ширхэг $b_1, b_2, ..., b_{|b|} (1\le b_i\le 10^5)$ бүхэл тоонууд өгөгдөнө.

Гаралт

Нэг мөрөнд олсон нийлбэрээ $|b|^2$-д хувааж хэвлэ. Нарийвчлалын алдаа $10^{-6}$-аас ихгүй бол хариу зөвд тооцогдоно.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
5
1 2 3 4 1
Гаралт
1.238750000000000
Сэтгэгдлүүдийг ачааллаж байна...