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: interview

Starter code:

Solutions:
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 = list(map(int,input().split()))
a = list(map(int,input().split()))
print(sum(a)-solve(a,n)+solve(a,n)/k)


# cook your dish here
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)

# cook your dish here
def atharva(a:list,n:int): 
 msf = a[0]
 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)

# cook your dish here
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 = list(map(int,input().split()))
t = sum(a)
u = maxSubArraySum(a,n)
print(t-u+u/x)

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 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 = list(map(int,input().split()))
t = sum(a)
u = maxSubArraySum(a,n)
print(t-u+u/x)

# cook your dish here
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))





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


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,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,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())
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)))

n,m=list(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)


# cook your dish here
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))





 


n,k=list(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)
  
  
   


# cook your dish here
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))

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)


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

print(min((p-maxi+maxi/x),(p-mini+mini/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)