#include "kanapka.h"
#include "message.h"
#include <bits/stdc++.h>
using namespace std;

pair<int, int> getStartEnd(int n, int nodeID, int totalNodes){
	// oblicz początek i koniec.
	int nodesPerInstance = ceil((double)n / (double)totalNodes);
	int start = nodeID * nodesPerInstance;
	int end = start + nodesPerInstance - 1;
	if(end >= n){
		end = n - 1;
	}
	return pair<int, int>(start, end);
}

int main(){
	int n = GetN();
	int myNode = MyNodeId();
	int totalNodes = NumberOfNodes();
	pair<int, int> startEnd = getStartEnd(n, myNode, totalNodes);
	int start = startEnd.first;
	int end = startEnd.second;
	
	long long sum = 0;
	long long max_prefix = 0;
	long long min_prefix = 0;
	long long max_suffix;
	long long max_infix = 0;	
	long long current_infix = 0;
	
	for(int i = start; i <= end; ++i){
		// odwracam liczby na ujemne, obliczam najnizsze mozliwe podslowo
		long long value = - GetTaste(i);
		sum += value;
		current_infix += value;
		if(sum > max_prefix){
			max_prefix = sum;
		}
		if(sum < min_prefix){
			min_prefix = sum;
		}
		if(current_infix < 0){
			current_infix = 0;
		}
		if(current_infix > max_infix){
			max_infix = current_infix;
		}
	}
	max_suffix = sum - min_prefix;
	
	if(myNode > 0){
		PutLL(0, sum);
		PutLL(0, max_prefix);
		PutLL(0, max_suffix);
		PutLL(0, max_infix);
		Send(0);
	}else{
		long long totalSum = sum;
		long long bestResult = max_infix;
		long long values[totalNodes][3];
		values[0][0] = sum;
		values[0][1] = max_prefix;
		values[0][2] = max_suffix;
		
		for(int i = 1; i < totalNodes; ++i){
			int idx = Receive(-1);
			for(int j = 0; j < 3; ++j){
				values[idx][j] = GetLL(idx);
			}
			long long infixV = GetLL(idx);
			
			if(infixV > bestResult){
				bestResult = infixV;
			}
			totalSum += values[idx][0];
		}
		
		long long left[totalNodes];
		long long right[totalNodes];
		
		left[0] = values[0][2];
		for(int i = 1; i < totalNodes; ++i){
			left[i] = max(left[i - 1] + values[i][0], values[i][2]);
		}
		
		right[totalNodes - 1] = values[totalNodes - 1][1];
		for(int i = totalNodes - 2; i >= 0; --i){
			right[i] = max(right[i + 1] + values[i][0], values[i][1]);
		}
		
		for(int i = 1; i < totalNodes; ++i){
			// liczymy pare (i-1, i)
			long long result = left[i - 1] + right[i];
			if(result > bestResult){
				bestResult = result;
			}
		}
		
		bestResult = -(totalSum - bestResult);
		cout << bestResult << endl;
	}
	return 0;
}