You are given a sequence of integers $A_1,A_2,…,A_N$ and a magical non-zero integer $x$
You have to select a subsegment of sequence A (possibly empty), and replace the elements in that subsegment after dividing them by x.
Formally, replace any one subsegment $A_l, A_{l+1}, ..., A_r$ with $A_l/x, A_{l+1}/x, ..., A_r/x$ where $l \leq r$
What is the minimum possible sum you can obtain?
Note: The given operation can only be performed once

-----Input -----
- The first line of the input contains two positive integer n denoting the size of array, and x
denoting the magical integer
- Next line contains $N$ space separated integers

-----Output-----
Single line containing one real number, denoting the minimum possible sum you can obtain. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-2}$

-----Constraints-----
- $1 \leq n \leq 10^3$
- $1 \leq |x| \leq 10^3$
- $ |A_i| \leq 10^3$

-----Sample Input-----
3 2
1 -2 3

-----Sample Output-----
0.5

-----Explanation-----
Array 1 -2 3, selecting subsegment {3}, you get 1 -2 1.5, which gives $sum=0.5$

Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
(n, x) = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
if n == 1:
	if r[0] > 0:
		print(r[0])
	else:
		print(r[0] / x)
else:
	st = n - 1
	en = n - 1
	sums = [0] * n
	sums[-1] = r[-1]
	s = r[-1]
	while st > 0:
		st -= 1
		if s > 0:
			s += r[st]
		else:
			s = r[st]
			en = st
		sums[st] = s
	print(sum(r) - max(sums) + max(sums) / x)


def find_max_subarray(alist, start, end):
	if start == end - 1:
		return (start, end, alist[start])
	else:
		mid = (start + end) // 2
		(left_start, left_end, left_max) = find_max_subarray(alist, start, mid)
		(right_start, right_end, right_max) = find_max_subarray(alist, mid, end)
		(cross_start, cross_end, cross_max) = find_max_crossing_subarray(alist, start, mid, end)
		if left_max > right_max and left_max > cross_max:
			return (left_start, left_end, left_max)
		elif right_max > left_max and right_max > cross_max:
			return (right_start, right_end, right_max)
		else:
			return (cross_start, cross_end, cross_max)

def find_max_crossing_subarray(alist, start, mid, end):
	sum_left = float('-inf')
	sum_temp = 0
	cross_start = mid
	for i in range(mid - 1, start - 1, -1):
		sum_temp = sum_temp + alist[i]
		if sum_temp > sum_left:
			sum_left = sum_temp
			cross_start = i
	sum_right = float('-inf')
	sum_temp = 0
	cross_end = mid + 1
	for i in range(mid, end):
		sum_temp = sum_temp + alist[i]
		if sum_temp > sum_right:
			sum_right = sum_temp
			cross_end = i + 1
	return (cross_start, cross_end, sum_left + sum_right)
x = input().split()
n = int(x[0])
m = int(x[1])
list = []
y = input().split()
for i in range(n):
	list.append(int(y[i]))
sum1 = sum(list)
(start, end, max1) = find_max_subarray(list, 0, len(list))
print(sum1 - max1 + max1 / m)


def maxSubArraySum(a, size):
	(max_so_far, curr_max) = (a[0], a[0])
	for i in range(1, size):
		curr_max = max(a[i], curr_max + a[i])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far
(n, x) = map(int, input().split())
a = list(map(int, input().split()))
print(sum(a) - maxSubArraySum(a, n) + maxSubArraySum(a, n) / x)


def solve(N, X, A):
	prefix = A[:]
	for i in range(1, N):
		prefix[i] += prefix[i - 1]
	maxx = 0
	for i in range(0, N):
		for j in range(i, N):
			maxx = max(maxx, prefix[j] - prefix[i] + A[i])
	print(prefix[N - 1] - (maxx - maxx / X))
(N, X) = map(int, input().split())
A = list(map(int, input().split()))
solve(N, X, A)


def atharva(a: list, n: int):
	msf = mh = a[0]
	for i in range(n):
		mh = max(a[i], mh + a[i])
		msf = max(msf, mh)
	return msf
(n, x) = map(int, input().split())
a = list(map(int, input().split()))
summ = sum(a)
max_sum = atharva(a, len(a))
print(summ - max_sum + max_sum / x)


def get_the_largest_contiguous_subarray_sum(A, N):
	max_sum_so_far = 0
	max_sum_ending_here = 0
	for i in range(N):
		max_sum_ending_here += A[i]
		if max_sum_ending_here < 0:
			max_sum_ending_here = 0
		else:
			max_sum_so_far = max(max_sum_so_far, max_sum_ending_here)
	return max_sum_so_far
(N, x) = list(map(int, input().split()))
A = list(map(int, input().split()))
array_sum = sum(A)
max_subarray_sum = get_the_largest_contiguous_subarray_sum(A, N)
profit = max_subarray_sum - max_subarray_sum / x
min_sum_possible = array_sum - profit
print(min_sum_possible)


(_, x) = map(int, input().split(' '))
lst = [int(f) for f in input().split()]
k = 0
l = 0
maxsum = 0
currsum = 0
sumall = 0
for i in lst:
	sumall += i
	currsum += i
	maxsum = max(maxsum, currsum)
	if currsum < 0:
		currsum = 0
print(sumall - maxsum * (1 - 1 / x))


(n, x) = list(map(int, input().split()))
a = list(map(int, input().split()))
maxi = a[0]
p = 0
for i in range(n):
	sumi = a[i]
	if sumi > maxi:
		maxi = sumi
	for j in range(i + 1, n):
		sumi += a[j]
		if i == 0:
			p += a[j]
		if sumi > maxi:
			maxi = sumi
	if sumi > maxi:
		maxi = sumi
p += a[0]
print(p - maxi + maxi / x)


(m, n) = map(int, input().split())
a = list(map(int, input().split()))
t = -1000000
for x in range(m):
	s = 0
	for y in range(x, m):
		s += a[y]
		if s > t:
			t = s
d = sum(a)
print(min(d, d - t + t / n))


(n, x) = map(int, input().split())
arr = list(map(int, input().split()))
max_subarray_sum = 0
temp_sum = 0
total_sum = 0
for i in arr:
	total_sum += i
	temp_sum += i
	max_subarray_sum = max(temp_sum, max_subarray_sum)
	if temp_sum < 0:
		temp_sum = 0
		continue
print(total_sum - max_subarray_sum + max_subarray_sum / x)


from math import log

def maxSubArraySum(a, size):
	max_so_far = 0
	max_ending_here = 0
	l = 0
	r = 0
	beg = 0
	for j in range(0, size):
		max_ending_here = max_ending_here + a[j]
		if max_ending_here < 0:
			max_ending_here = 0
			beg = j + 1
		elif max_so_far < max_ending_here:
			l = beg
			r = j
			max_so_far = max_ending_here
	return (max_so_far, l, r)
(n, x) = map(int, input().split())
a = list(map(int, input().split()))
t = 0
for i in a:
	if i >= 0:
		t = 1
if t == 0:
	print(sum(a))
else:
	(sum1, l, r) = maxSubArraySum(a, n)
	for i in range(l, r + 1):
		a[i] = a[i] / x
	sum = 0
	for i in a:
		sum = sum + i
	print(sum)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
sumi = 0
ans = 10 ** 20
for i in range(len(a)):
	sumi = sum(a)
	for j in range(i, len(a)):
		sumi = sumi - a[j] + a[j] / k
		ans = min(ans, sumi)
print(ans)


(n, x) = map(int, input().split())
l = [*map(int, input().split())]
s = [0]
for e in l:
	s.append(s[-1] + e)
res = s[-1]
for i in range(n):
	for j in range(i, n):
		ans = s[i] + (s[j + 1] - s[i]) / x + (s[-1] - s[j + 1])
		res = min(res, ans)
print(res)


(n, x) = map(int, input().split())
l = [int(x) for x in input().split()]
s = sum(l)
left = [0]
right = [0] * (n + 1)
for i in range(n):
	left.append(left[i] + l[i])
	right[n - i - 1] = right[n - i] + l[n - i - 1]
del left[0]
del right[-1]
for i in range(n):
	tempSum = 0
	for j in range(i, n, 1):
		tempSum += l[j] / x
		ls = left[i - 1] if i != 0 else 0
		rs = right[j + 1] if j != n - 1 else 0
		s = min(s, ls + rs + tempSum)
print(s)


def solve():
	(n, x) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	total = sum(arr)
	(maxi, sum_) = (0, 0)
	for i in range(n):
		sum_ += arr[i]
		maxi = max(sum_, maxi)
		if sum_ <= 0:
			sum_ = 0
	return total - maxi + maxi / x
print(solve())


(n, x) = [int(a) for a in input().split(' ') if a != '']
arr = [int(a) for a in input().split(' ') if a != '']
total = sum(arr)
total_max = arr[0]
current_max = arr[0]
for i in range(1, n):
	current_max = max(arr[i], current_max + arr[i])
	total_max = max(current_max, total_max)
print(total - total_max + total_max / x)


def maxsum(a, size):
	max_so_far = a[0]
	curr_max = a[0]
	for i in range(1, size):
		curr_max = max(a[i], curr_max + a[i])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far
(n, x) = map(int, input().split())
a = list(map(int, input().split()))
q = maxsum(a, n)
if q >= 0:
	print(sum(a) - q + q / x)
else:
	print(sum(a))


(n, x) = input().split()
n = int(n)
x = int(x)
arr = input().split()
for i in range(len(arr)):
	arr[i] = int(arr[i])
max_included_arr = [0] * n
max_not_included_arr = [0] * n
max_included_arr[0] = arr[0]
max_not_included_arr[0] = 0
for i in range(1, len(arr)):
	max_included_arr[i] = max(max_included_arr[i - 1] + arr[i], arr[i])
	max_not_included_arr[i] = max(max_included_arr[i - 1], max_not_included_arr[i - 1])
max_subsum = max(max_included_arr[-1], max_not_included_arr[-1])
total_sum = sum(arr)
min_included_arr = [0] * n
min_not_included_arr = [0] * n
min_included_arr[0] = arr[0]
min_not_included_arr[0] = 0
for i in range(1, len(arr)):
	min_included_arr[i] = min(min_included_arr[i - 1] + arr[i], arr[i])
	min_not_included_arr[i] = min(min_included_arr[i - 1], min_not_included_arr[i - 1])
min_subsum = min(min_not_included_arr[-1], min_included_arr[-1])
answer1 = total_sum - max_subsum + max_subsum / x
answer2 = total_sum - min_subsum + min_subsum / x
print(min(answer1, answer2))


def max_subarray_sum(a):
	max_till_now = 0
	max_ending_here = 0
	minused = 1000000000
	for i in range(len(a)):
		max_ending_here = max_ending_here + a[i]
		if max_ending_here < 0:
			max_ending_here = 0
		if max_ending_here > max_till_now:
			max_till_now = max_ending_here
	return max_till_now
(n, x) = map(int, input().strip().split(' '))
l = list(map(int, input().strip().split(' ')))
m = max_subarray_sum(l)
print(sum(l) - m + m / x)


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
mx = -9999999999999999
cs = 0
for i in range(n):
	cs += a[i]
	if mx < cs:
		mx = cs
	if cs < 0:
		cs = 0
s = float(sum(a) - mx + mx / x)
print('%.2f' % s)


(n, x) = list(map(int, input().strip().split()))
array = list(map(int, input().strip().split()))
sumList = list()
i = 0
sumelem = 0
maxSum = float('-inf')
for i in array:
	sumelem += i
	if sumelem < 0:
		sumelem = 0
	maxSum = max(maxSum, sumelem)
print('{:.2f}'.format(sum(array) - maxSum + maxSum / x))


(n, x) = map(int, input().split())
l = list(map(int, input().split()))
ans = l[0]
temp = l[0]
for i in range(1, n):
	temp = max(l[i], temp + l[i])
	ans = max(temp, ans)
print(sum(l) - ans + ans / x)


from sys import maxsize as maxint

def maxS(a, size):
	max_so_far = -maxint - 1
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far
(n, x) = map(int, input().split())
l = list(map(int, input().split()))
f = maxS(l, n)
print(sum(l) - f + f / x)


(a, b) = map(int, input().split())
c = list(map(int, input().split()))
s = sum(c)
l = sum(c)
g = sum(c)
f = []
for i in range(a):
	for j in range(i, a):
		l = l - c[j] + c[j] / b
		if l < s:
			s = l
	f.append(s)
	l = g
	s = g
print(min(f))


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
maxsum = 0
allsum = 0
currsum = 0
for i in a:
	currsum += i
	allsum += i
	maxsum = max(maxsum, currsum)
	if currsum < 0:
		currsum = 0
print(allsum - (maxsum - maxsum / x))


from bisect import bisect_left, bisect_right
import math
from sys import maxsize
from collections import defaultdict
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
nx = il()
n = nx[0]
x = nx[1]
ls = il()
msf = -maxsize - 1
meh = 0
st = -1
e = -1
s = 0
for i in range(n):
	meh += ls[i]
	if msf < meh:
		msf = meh
		st = s
		e = i
	if meh < 0:
		meh = 0
		s = i + 1
s = 0
for i in range(0, st):
	s = s + ls[i]
if e + 1 != n:
	for k in range(e + 1, n):
		s = s + ls[k]
s = s + msf / x
print(s)


(n, x) = map(int, input().split())
N = list(map(int, input().split()))
dp = [0] * n
dp[0] = N[0]
for i in range(1, n):
	dp[i] = max(N[i], dp[i - 1] + N[i])
m = max(dp)
print(sum(N) - m + m / x)


(n, x) = map(int, input().split())
arr = [int(x) for x in input().split()]
asum = sum(arr)
minsum = min(asum, asum / x)
rest = 0
for i in range(1, n):
	asum = asum - arr[-i]
	rest += arr[-i]
	minsum = min(minsum, rest + asum / x)
	temp = rest
	tempsum = asum
	for j in range(i):
		tempsum = tempsum - arr[j] + arr[n - i + j]
		temp = temp + arr[j] - arr[j + n - i]
		minsum = min(minsum, temp + tempsum / x)
print(minsum)


(n, x) = map(int, input().split())
arr = list(map(int, input().split()))
arr1 = []
for i in range(n):
	narr = arr.copy()
	for j in range(i, n):
		narr[j] = narr[j] / x
		arr1.append(sum(narr))
print(min(arr1))


(n, x) = map(int, input().split())
l = list(map(int, input().split()))
m = []
for i in range(len(l)):
	for j in range(i, len(l)):
		m.append(sum(l[i:j + 1]))
a = min(m)
b = max(m)
s = sum(l)
if b > 0:
	print(s - b + b / x)
elif b < 0:
	print(s)
else:
	print(s)


(n, k) = map(int, input().split())
arr = list(map(int, input().split()))
sum_arr = [0] * n
sum_arr[0] = arr[0]
partial = arr[0]
for i in range(1, n):
	partial += arr[i]
	sum_arr[i] = partial
sum_arr.insert(0, 0)
max_var = sum_arr[1] - sum_arr[0]
for i in range(1, n + 1):
	for j in range(i):
		if max_var <= sum_arr[i] - sum_arr[j]:
			max_var = sum_arr[i] - sum_arr[j]
print('%0.1f' % (sum(arr) + max_var * (1 / k - 1)))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
(inc, enc) = (0, 0)
for i in range(0, len(l)):
	inc = max(l[i], inc + l[i])
	enc = max(enc, inc)
result = sum(l) - enc
print(result + enc / m)


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
b = []
i = 0
while i < n:
	j = i + 1
	while j <= n:
		b.append([sum(a[i:j]), i, j])
		j += 1
	i += 1
b.sort()
l = len(b)
v = b[l - 1][1]
y = b[l - 1][2]
z = b[l - 1][0]
print(float(sum(a[0:v]) + sum(a[y:n]) + z / x))


def solve(a, n):
	max1 = curr = a[0]
	for i in range(1, n):
		curr = max(a[i], curr + a[i])
		max1 = max(max1, curr)
	return max1
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
print(sum(a) - solve(a, n) + solve(a, n) / k)


(n, x) = map(int, input().split())
arr = [int(a) for a in input().split(' ') if a != '']
Total_sum = sum(arr)
max_sum = arr[0]
curr_sum = arr[0]
for i in range(1, len(arr)):
	curr_sum = max(arr[i], curr_sum + arr[i])
	max_sum = max(curr_sum, max_sum)
print(Total_sum - max_sum + max_sum / x)


(n, x) = map(int, input().split())
y = list(map(int, input().split()))
p = y[:]
for j in range(1, len(y)):
	p[j] += p[j - 1]
max_sum = 0
for j in range(n):
	for k in range(j, n):
		max_sum = max(max_sum, p[k] - p[j] + y[j])
print(p[n - 1] - (max_sum - max_sum / x))


(n, x) = map(int, input().split())
l = list(map(int, input().split()))
mini1 = 10 ** 18
mini2 = 10 ** 18
sum3 = sum(l)
for i in range(n):
	sum1 = 0
	sum2 = 0
	for j in range(i, n):
		sum1 += l[j]
		sum2 += l[j] / x
		new_sum = sum3 - sum1 + sum2
		if new_sum < mini1:
			mini1 = new_sum
print(min(mini1, sum3))


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
b = sum(a)
summ = []
summ.append(b)
for i in range(n):
	summm = b
	for j in range(i, n):
		summm += a[j] / x - a[j]
		summ.append(summm)
print(min(summ))


def func1(l):
	if len(l) == 1:
		return 0
	elif len(l) == 2:
		return l[1] - l[0]
	else:
		mid = len(l) // 2
		p = l[:mid]
		q = l[mid:]
		return max(func1(p), func1(q), max(q) - min(p))

def func2(l):
	if len(l) == 1:
		return float('inf')
	elif len(l) == 2:
		return l[1] - l[0]
	else:
		mid = len(l) // 2
		p = l[:mid]
		q = l[mid:]
		return min(func2(p), func2(q), min(q) - max(p))
(n, x) = list(map(int, input().split()))
arr = list(map(int, input().split()))
l = [0]
for i in arr:
	l.append(l[-1] + i)
l.pop(0)
if x == 1:
	print(l[-1])
elif 1 / x - 1 < 0:
	v = func1(l)
else:
	v = func2(l)
print(l[-1] - v + v / x)


(n, x) = [int(_) for _ in input().split()]
l = [int(_) for _ in input().split()]
bit = [0] * (len(l) + 1)
total = 0
max = None
index = None
for i in range(len(l)):
	total = l[i]
	if max == None or total > max:
		max = total
		index = (i, i)
	for j in range(i + 1, len(l)):
		total += l[j]
		if total > max:
			max = total
			index = (i, j)
for i in range(index[0], index[1] + 1):
	l[i] /= x
print(sum(l))


c = [int(a) for a in input().split()]
n = c[0]
x = c[1]
A = [int(a) for a in input().split()]
tots = 0
tems = 0
maxs = 0
for i in A:
	tots += i
	tems += i
	maxs = max(maxs, tems)
	if tems < 0:
		tems = 0
op = tots - maxs * (1 - 1 / x)
print(op)


import sys
mod = 1000000007
get_arr = lambda : list(map(int, input().split()))
get_int = lambda : int(input())
get_ints = lambda : map(int, input().split())
get_str = lambda : input()
get_strs = lambda : input().split()
from math import log
(n, x) = get_ints()
A = get_arr()
tot = sum(A) * 1.0
start = 0
end = 0
curr_max = 0
prev_max = 0
start_o = 0
for i in range(n):
	curr_max += A[i]
	if curr_max < 0:
		start = i + 1
		curr_max = 0
	elif curr_max > prev_max:
		end = i
		start_o = start
		prev_max = curr_max
for i in range(start_o, end + 1):
	tot -= A[i]
	tot += A[i] * 1.0 / x
print(tot)


from sys import maxsize

def maxSubArraySum(a, size):
	max_so_far = -maxsize - 1
	max_ending_here = 0
	start = 0
	end = 0
	s = 0
	for i in range(0, size):
		max_ending_here += a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
			start = s
			end = i
		if max_ending_here < 0:
			max_ending_here = 0
			s = i + 1
	return (start, end)
(n, x) = map(int, input().split())
a = [int(i) for i in input().split()]
if all([i < 0 for i in a]):
	print(sum(a))
else:
	(start, end) = maxSubArraySum(a, n)
	print(sum(a[0:start]) + sum(a[start:end + 1]) / x + sum(a[end + 1:]))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
i = 0
x = sum(l)
d = x
m = 0
for i in range(n):
	c = 0
	for j in range(i, n):
		c += l[j]
		m = max(c, m)
d -= m
d += m / k
print(d)


(n, x) = list(map(int, input().split()))
lst = list(map(int, input().split()))
(s, t, tot) = (0, 0, 0)
for i in lst:
	tot = tot + i
	t = t + i
	s = max(s, t)
	if t < 0:
		t = 0
		continue
print(tot - s + s / x)


def maxSubArraySum(a, size):
	max_so_far = -10 ** 9 - 1
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far
(n, x) = map(int, input().split())
l = list(map(int, input().split()))
val = maxSubArraySum(l, n)
print('%.2f' % (sum(l) - val + val / x))


def maxSubArraySum(arr, n, x):
	max_so_far = arr[0]
	max_ending_here = arr[0]
	start = 0
	end = 0
	beg = 0
	for i in range(1, n):
		max_ending_here = max_ending_here + arr[i]
		if max_ending_here < arr[i]:
			max_ending_here = arr[i]
			beg = i
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
			start = beg
			end = i
	s = 0
	for i in range(len(arr)):
		if i >= start and i <= end:
			s = s + arr[i] / x
		else:
			s = s + arr[i]
	return s
(N, x) = map(int, input().split())
l = list(map(int, input().split()))
a = maxSubArraySum(l, len(l), x)
print('{0:.2f}'.format(a))


def max_possible_sum_of_subsegment(array):
	current_max = 0
	maxx = 0
	for j in array:
		current_max += j
		if maxx < current_max:
			maxx = current_max
		if current_max < 0:
			current_max = 0
	return maxx
(n, x) = list(map(int, input().split()))
l = list(map(int, input().split()))
tot = sum(l)
maxx = max_possible_sum_of_subsegment(l)
print(tot - maxx + maxx / x)


(n, x) = list(map(int, input().split()))
a = list(map(int, input().split()))
total = sum(a)
current_max = a[0]
total_max = a[0]
for i in range(1, len(a)):
	current_max = max(a[i], current_max + a[i])
	total_max = max(total_max, current_max)
print(total - total_max + total_max / x)


tmp = [int(x) for x in input().split()]
n = tmp[0]
x = tmp[1]
arr = [int(x) for x in input().split()]
maxs = 0
(s, e) = (0, n - 1)
for i in range(n):
	tmp = 0
	for j in range(i, n):
		tmp += arr[j]
		if j == 0 and i == 0:
			maxs = tmp
			s = i
			e = j
		elif maxs < tmp:
			maxs = tmp
			s = i
			e = j
fsum = 0
for i in range(n):
	if i >= s and i <= e:
		arr[i] = float(arr[i] / x)
	fsum += float(arr[i])
print(fsum)


def maxSubArraySum(a, size):
	max_so_far = -1 * 1001
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far
(n, x) = list(map(int, input().split()))
arr = list(map(int, input().split()))
max_sum = maxSubArraySum(arr, n)
print(sum(arr) - max_sum + max_sum / x)


def maxSubArraySum(a, size):
	max_so_far = -1000000000
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
		if max_ending_here < 0:
			max_ending_here = 0
	return max_so_far
(n, x) = [int(i) for i in input().split()]
lis = [int(i) for i in input().split()]
init = sum(lis)
if x == 0:
	print(init)
else:
	useme = maxSubArraySum(lis, n)
	print(min(init, init - (x - 1) * useme / x))


(N, X) = map(int, input().split())
A = list(map(int, input().split()))
lst = []
s = 0
psum = A[:]
for i in range(1, N):
	psum[i] += psum[i - 1]
m = -9999999
for i in range(0, N):
	for j in range(i, N):
		m = max(m, psum[j] - psum[i] + A[i])
print(psum[-1] - m + m / X)


y = input().split()
n = int(y[0])
x = int(y[1])
F = [int(f) for f in input().split()]
t1 = 0
t2 = 0
upma = 0
for i in F:
	t1 += i
	t2 += i
	upma = max(upma, t2)
	if t2 < 0:
		t2 = 0
print(t1 - upma * (1 - 1 / x))


def ma(a):
	kt = 0
	for i in a:
		if i > 0:
			kt = 1
			break
	if kt == 0:
		return max(a)
	ma = 0
	cur = 0
	for i in a:
		cur += i
		if cur < 0:
			cur = 0
		if cur > ma:
			ma = cur
	return ma
(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
s = sum(a)
cu = 0
s1 = ma(a)
s2 = s - s1
s1 = s1 / m + s2
print(round(s1, 2))


def maxsum(a):
	max_so_far = a[0]
	max_ending_here = 0
	for i in range(0, len(a)):
		max_ending_here = max_ending_here + a[i]
		if max_ending_here < 0:
			max_ending_here = 0
		elif max_so_far < max_ending_here:
			max_so_far = max_ending_here
	return max_so_far
(a, x) = (input().split(), input().split())
k = int(a[1])
x = [int(x[i]) for i in range(len(x))]
print(sum(x) - maxsum(x) + maxsum(x) / k)


def maxSubArraySum(a, size, lk):
	max_so_far = 0
	max_ending_here = 0
	start = 0
	end = 0
	s = 0
	for i in range(0, size):
		max_ending_here += a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
			start = s
			end = i
		if max_ending_here < 0:
			max_ending_here = 0
			s = i + 1
	sum1 = sum(a[0:start])
	sum2 = sum(a[start:end + 1]) / lk
	sum3 = sum(a[end + 1:])
	print(sum1 + sum2 + sum3)
q = input().split()
a = int(q[0])
b = int(q[1])
w = input().split()
for i in range(a):
	w[i] = int(w[i])
maxSubArraySum(w, a, b)


def maxSubArraySum(a, size):
	max_so_far = a[0]
	curr_max = a[0]
	for i in range(1, size):
		curr_max = max(a[i], curr_max + a[i])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far
(n, k) = [int(x) for x in input().strip().split()]
arr = [int(x) for x in input().strip().split()]
oldsum = sum(arr)
maxsumsub = maxSubArraySum(arr, n)
print(round(oldsum - maxsumsub + maxsumsub / k, 2))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
k = []
for i in range(n):
	sum1 = 0
	for j in range(i, n):
		sum1 = sum1 + l[j]
		k.append(sum1)
d = max(k)
print(min(sum(l), sum(l) - d + d / m))


(n, x) = list(map(int, input().split()))
arr = list(map(int, input().split()))
l = 0
r = 0
suma = 0
maxa = 0
count = 0
for i in range(n):
	if suma == 0:
		left = i
	suma += arr[i]
	if arr[i] > 0:
		count += 1
	right = i
	if suma < 0:
		suma = 0
	if suma > maxa:
		maxa = suma
		l = left
		r = right
ans = 0
if count == 0:
	print('%.4f' % sum(arr))
else:
	for i in range(n):
		if i >= l and i <= r:
			ans += arr[i] / x
		else:
			ans += arr[i]
	print('%.4f' % ans)


from sys import maxsize
nx = list(map(int, input().strip().split()))
n = nx[0]
x = nx[1]
ls = list(map(int, input().strip().split()))
msf = -maxsize - 1
meh = 0
st = -1
e = -1
s = 0
for i in range(n):
	meh += ls[i]
	if msf < meh:
		msf = meh
		st = s
		e = i
	if meh < 0:
		meh = 0
		s = i + 1
sumation = 0
for i in range(0, st):
	sumation = sumation + ls[i]
if e + 1 != n:
	for k in range(e + 1, n):
		sumation = sumation + ls[k]
sumation = sumation + msf / x
print(sumation)


(n, x) = map(int, input().split())
L = list(map(int, input().split()))
add = 0
for i in range(n):
	for j in range(i + 1, n + 1):
		s = sum(L[i:j])
		if s >= add:
			add = s
a = sum(L)
print(a - add + add / x)


for _ in range(1):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	mx = -1e+17
	s = 0.0
	f = 0.0
	for i in range(n):
		s += a[i]
		f += a[i]
		mx = max(mx, s)
		if s < 0.0:
			s = 0.0
		mx = max(mx, s)
	ans = f - mx + mx / x
	print('%.5f' % ans)


ll = lambda : list(map(int, input().split()))
[n, x] = ll()
arr = ll()
mins = 99999999
ps = [0]
for i in range(n):
	ps.append(ps[-1] + arr[i])
for i in range(n):
	subsum = [0] * n
	for j in range(i, n):
		ans = ps[i] + (ps[j + 1] - ps[i]) / x + ps[-1] - ps[j]
		if ans < mins:
			mins = ans
print(round(mins, 1))


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
max_so_far = -10000000
max_ending_here = 0
finish = -1
start = 0
for i in range(n):
	max_ending_here = max_ending_here + a[i]
	if max_so_far < max_ending_here:
		max_so_far = max_ending_here
		finish = i
	if max_ending_here < 0:
		max_ending_here = 0
s = 0
a.reverse()
finish = n - finish - 1
if finish != -1:
	for i in range(finish, n):
		s = s + a[i]
		if s == max_so_far:
			start = i
			break
else:
	finish = n - 1
(start, finish) = (finish, start)
print(sum(a[:start]) + sum(a[finish + 1:]) + sum(a[start:finish + 1]) / x)


def maxSubArraySum(a, size):
	max_so_far = a[0]
	curr_max = a[0]
	for i in range(1, size):
		curr_max = max(a[i], curr_max + a[i])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far
(n, x) = map(int, input().split())
a = [int(j) for j in input().split()]
maxi = maxSubArraySum(a, len(a))
sum1 = sum(a)
print(sum1 - maxi + maxi / x)


def kadanes(a, n):
	curr = 0
	maxi = 0
	for i in a:
		curr += i
		maxi = max(curr, maxi)
		if curr < 0:
			curr = 0
	return maxi
(n, x) = map(int, input().split())
a = list(map(int, input().split()))
maxsum = kadanes(a, n)
s = sum(a)
div = maxsum / x
print(s - maxsum + div)


(n, x) = list(map(int, input().split()))
a = list(map(int, input().rstrip().split()))
max_so_far = 0
max_end_here = 0
for i in a:
	max_end_here += i
	max_end_here = max(0, max_end_here)
	max_so_far = max(max_so_far, max_end_here)
print(sum(a) - max_so_far + max_so_far / x)


from sys import maxsize

def maxSubArraySum(a, size):
	max_so_far = -maxsize - 1
	max_ending_here = 0
	start = 0
	end = 0
	s = 0
	for i in range(0, size):
		max_ending_here += a[i]
		if max_so_far < max_ending_here:
			max_so_far = max_ending_here
			start = s
			end = i
		if max_ending_here < 0:
			max_ending_here = 0
			s = i + 1
	return (start, end)
(n, k) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
(i, j) = maxSubArraySum(arr, n)
for ii in range(i, j + 1):
	arr[ii] = arr[ii] / k
print(round(sum(arr), 2))


(n, x) = map(int, input().split())
(s, mn, mx) = (0, 0, 0)
for v in map(int, input().split()):
	s += v
	if s < mn:
		mn = s
	if s - mn > mx:
		mx = s - mn
print(s - mx + mx / x)


def SubarrayWithMaxSum(nums):
	currMax = nums[0]
	globalMax = nums[0]
	for i in range(1, len(nums)):
		currMax = max(nums[i], nums[i] + currMax)
		if currMax > globalMax:
			globalMax = currMax
			endIndex = i
	startIndex = endIndex
	while startIndex >= 0:
		globalMax -= nums[startIndex]
		if globalMax == 0:
			break
		startIndex -= 1
	c = 0
	for i in range(startIndex, endIndex + 1):
		c += nums[i]
	return c
[N, x] = [float(i) for i in input().split()]
arr = [int(i) for i in input().split()]
summ = sum(arr)
cnt = SubarrayWithMaxSum(arr)
print(summ - cnt + cnt / x)


(n, x) = map(int, input().split())
arr = list(map(int, input().split()))
start = 0
end = 0
summ = 0
maxstart = 0
maxend = 0
maxsumm = 0
for i in range(len(arr)):
	if summ == 0:
		start = i
	summ += arr[i]
	if summ <= 0:
		start = i + 1
		end = i + 1
		summ = 0
	elif summ > maxsumm:
		maxstart = start
		maxend = i
		maxsumm = summ
for i in range(maxstart, maxend + 1):
	arr[i] = arr[i] / x
newsumm = 0
for i in range(len(arr)):
	newsumm += arr[i]
print(newsumm)


def snek(a, n):
	m = a[0]
	c = a[0]
	for j in range(1, n):
		c = max(a[j], c + a[j])
		m = max(m, c)
	return m
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
print(sum(a) - snek(a, n) + snek(a, n) / k)


def solve():
	(n, t) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	max_sum = curr = 0
	for x in A:
		max_sum = max(max_sum, curr + x)
		curr = max(curr + x, 0)
	return sum(A) - max_sum + max_sum / t
print(solve())


def maxSubArraySum(a, size):
	max_so_far = 0
	max_ending_here = 0
	for i in range(0, size):
		max_ending_here = max_ending_here + a[i]
		if max_ending_here < 0:
			max_ending_here = 0
		elif max_so_far < max_ending_here:
			max_so_far = max_ending_here
	return max_so_far
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
print(sum(l) - maxSubArraySum(l, n) + maxSubArraySum(l, n) / m)


import fileinput
with fileinput.input() as f:
	(n, x) = [int(e) for e in f.readline().strip().split(' ', 1)]
	aP = [int(e) for e in f.readline().strip().split(' ')]
	if len(aP) != n:
		raise ValueError('input length mismatch')
	aN = [e / x for e in aP]
	PaP = [0]
	for e in aP:
		PaP.append(PaP[-1] + e)
	NaP = [0]
	for e in aN:
		NaP.append(NaP[-1] + e)
	best = PaP[-1]
	for s in range(1, n + 1):
		for e in range(s, n + 1):
			p1 = PaP[s - 1]
			p2 = NaP[e] - NaP[s - 1]
			p3 = PaP[-1] - PaP[e]
			c = p1 + p2 + p3
			if c < best:
				best = c
	print(best)


(n, x) = map(int, input().split())
l = list(map(int, input().split()))
m = -10000000000.0
s = sum(l)
su = 0.0
for i in l:
	su = su + i
	m = max(su, m)
	if su < 0:
		su = 0
print(s - m * (1 - 1 / x))