#include <iostream>
#include <string>
#include <cctype>
#include "message.h"
#include "kanapka.h"

#ifdef __DEB
#include <fstream>
#include <cstdio>
#endif

#define RAM_LIMIT	2000000
#define MINIMUM_N 100000

using namespace std;

struct WYNIKI_PROCESOW
{	
	int64_t suma;
	int64_t max_prawo;
	int64_t max_lewo;
	int64_t max;
	int32_t nstart, nstop;
};

int main()
{
	int  ilosc_procesow = NumberOfNodes();
	if(ilosc_procesow==1)
	{
		//brutal na szybko
		int64_t n = GetN();
		if (n > 10000000) n = 10000000;
		int64_t *max_prawo = new int64_t[n];
		int64_t *max_lewo = new int64_t[n];
		
		int64_t i = 0;
		int64_t max = 0;
		int64_t suma = 0;
		while(i < n)
		{
			suma += GetTaste(i);
			if (suma > max) max = suma;
			max_prawo[i] = max;
			i++;
		}
		
		suma = 0;
		max = 0;
		i = n-1;
		while(i>=0)
		{
			suma += GetTaste(i);
			if (suma > max) max = suma;
			max_lewo[i] = max;
			i--;
		}
		
	/*	i = 0;
		while(i < n)
		{
			cout << max_prawo[i] << " " << max_lewo[i] << endl;
			i++;
		}*/
		
		max = 0;
		int32_t dlai = -1;
		i = 0;
		while(i < n-1)
		{
			suma = max_prawo[i] + max_lewo[i+1];
			if (suma > max) 
			{
		//		cout << suma << " " << max_prawo[i] << " " << max_lewo[i+1] << endl;
				max = suma;
				dlai = i;
			}
			i++;
		}
#ifdef __DEB
		char nazwa_pliku[20]; sprintf(nazwa_pliku, "deb_0.txt");
		std::ofstream deb (nazwa_pliku, std::ofstream::out);
		
		int64_t imax = max_prawo[dlai];
		suma = 0;
		i = 0;
		while(i <= dlai)
		{
			deb << GetTaste(i) << " ";
			suma += GetTaste(i);
			if (max_prawo[i] == imax) break;
			i++;
		}

		deb << endl << "** " << suma << endl;
		deb << "od: " << i << endl;

		suma = 0;		
		imax = max_lewo[dlai+1];
		//deb << imax << endl;
		i = n-1;
		while(i > dlai)
		{
			deb << GetTaste(i) << " ";
			suma += GetTaste(i);
			if (max_lewo[i] == imax) break;
			i--;
		}
		deb << endl << "** " << suma << endl;
		deb << "do: " << i << endl;
				
#endif		
				
		cout << max << endl;
		
		delete[] max_prawo;
		delete[] max_lewo;
	}
	else
	{
		
		int32_t n = GetN();
		int32_t nstart, nstop;
		int nasz_proces = MyNodeId();

#ifdef __DEB
		char nazwa_pliku[20]; sprintf(nazwa_pliku, "deb_%d.txt", nasz_proces);
		std::ofstream deb (nazwa_pliku, std::ofstream::out);
#endif				

		if (n < MINIMUM_N)
		{
#ifdef __DEB
			deb << "Zostawienie jednego procesu";
#endif				
			if (!nasz_proces)
			{
				ilosc_procesow = 1;
				nstart = 0;
				nstop = n-1;
			}
			else
			{
				return 0;
			}
		}
		else
		{
			if (nasz_proces == ilosc_procesow-1)
			{
				//ostatni proces dostaje wszystko co poprzedni + jakieś wyrównanie jeśli zajdzie potrzeba
				int32_t tmp = n / ilosc_procesow;
				nstart = tmp * nasz_proces;
				nstop = n-1;
			}
			else
			{
				int32_t tmp = n / ilosc_procesow;
				nstart = tmp * nasz_proces;
				nstop = tmp * (nasz_proces+1) - 1;
			}
		}
		
		//ze wzg. na limit pamięci jeszcze ekstra dodatkowy podział zastosujemy
		
		int32_t wndil = nstop-nstart+1;

		if (wndil % RAM_LIMIT)
		{
			//niepodzielne
			wndil /= RAM_LIMIT;
			wndil++;
		}
		else
		{
			//podzielne
			wndil /= RAM_LIMIT;
		}
#ifdef __DEB
		deb << "wndil: "<<wndil<<endl;
		deb << "proces: " << nasz_proces << " " << nstart << " " << nstop << endl;
#endif
		
		WYNIKI_PROCESOW *wnd = new WYNIKI_PROCESOW[wndil];

		int64_t *p_max_prawo = new int64_t[RAM_LIMIT+20];
		int64_t *p_max_lewo = new int64_t[RAM_LIMIT+20];

		int32_t porcja_start = nstart;
		int wndnr = 0;
		
		while(porcja_start <= nstop)
		{
			int64_t suma_prawo = 0;
			int64_t max_prawo = 0;
			int64_t suma_lewo = 0;
			int64_t max_lewo = 0;

			int32_t i = porcja_start;
			int32_t j = i + RAM_LIMIT -1;
			if (j > nstop) j = nstop;
			int32_t roznica = j-i;
			int32_t k = 0;
			int32_t jstop = j;
#ifdef __DEB
		deb << "i: "<<i<<" j: "<<j<<endl;
#endif
			while(i <= jstop)
			{
				suma_prawo += GetTaste(i);
				if (suma_prawo > max_prawo)
				{
					max_prawo = suma_prawo;
				}
				p_max_prawo[k] = max_prawo;
				suma_lewo += GetTaste(j);
				if (suma_lewo > max_lewo)
				{
					max_lewo = suma_lewo;
				}
				p_max_lewo[roznica-k] = max_lewo;
				k++;
				i++;
				j--;
			}
			
			int64_t max = 0;
			int64_t suma = 0;
			if (roznica)
			{
				k = 0;
				while(k < roznica)
				{
					suma = p_max_prawo[k] + p_max_lewo[k+1];
					if (suma > max) max = suma;
					k++;
				}
			}
			else
			{
				max = suma_prawo;
			}
		
			wnd[wndnr].nstart = porcja_start;
			wnd[wndnr].nstop = jstop;
			wnd[wndnr].suma = suma_prawo;
			wnd[wndnr].max_prawo = max_prawo;
			wnd[wndnr].max_lewo = max_lewo;
			wnd[wndnr].max = max;
			
#ifdef __DEB
		deb << "*** [" << suma_prawo << "] " << max_prawo << " "  << " " << max_lewo << " max:" << max << endl;
		{int i = 0;
		while(i < roznica+1)
		{
			deb << p_max_prawo[i] << " " << p_max_lewo[i] << endl;
			i++;
		}}		
#endif

			wndnr++;
			porcja_start += RAM_LIMIT;
		}

#ifdef __DEB
		{int i = 0;
		while(i < wndil)
		{
			deb << "n: " << wnd[i].nstart << " " << wnd[i].nstop << endl;
			deb << "suma: " << wnd[i].suma << endl;
			deb << "prawo: " << wnd[i].max_prawo << endl;
			deb << "lewo: " << wnd[i].max_lewo << endl;
			deb << "max: " << wnd[i].max << endl << endl;
			i++;
		}}		
#endif
		
			//znamy już wyniki procesów, więc lecimy z obliczeniami
			int64_t max = 0;
			int64_t suma_prawo = 0;
			int64_t suma_lewo = 0;
			int32_t i = 0;
			while(i < wndil-1)
			{
				suma_prawo += wnd[i].max_prawo;
				
#ifdef __DEB
				deb << "suma_prawo+max_prawo[" << i << "]: " << suma_prawo << endl;
#endif
				
				suma_lewo = 0;
				int64_t suma;
				int32_t j = wndil-1;
				while(j>i)
				{
					suma_lewo += wnd[j].max_lewo;
#ifdef __DEB
				deb << "		suma_lewo+max_lewo[" << j << "]: " << suma_lewo << endl;
#endif
					suma = suma_lewo + suma_prawo;
					if (suma > max) 
					{
						max = suma;
#ifdef __DEB
				deb << " ** nowe max: " << suma << endl;
#endif
					}

					suma_lewo -= wnd[j].max_lewo;
					suma_lewo += wnd[j].suma;
					j--;
				}

				suma_prawo -= wnd[i].max_prawo;
				suma_prawo += wnd[i].suma;
				
				i++;
			}
//max = 0;
			//do tej pory sprawdzialiśmy przypadki pomiędzy zestawami, ale nie przypadki, kiedy wynik mógł być w jednym zestawie
			//a teraz trzeba przetestować co by było, gdyby wynik znajdował się dokładnie w jednym z zestawów
			i = 0;
			while(i < wndil)
			{
				int64_t suma = 0;
				int32_t j = 0;
				while(j < wndil)
				{
					if (j != i)
					{
						suma += wnd[j].suma;
					}
					else
					{
						suma += wnd[j].max;
					}
					j++;
				}
				if (suma > max)
				{
					max = suma;
					#ifdef __DEB
									deb << " ** nowe max: " << suma << " dla: " << i << endl;
					#endif
				}
				i++;
			}						
		
			WYNIKI_PROCESOW dosend;
			dosend.nstart = nstart;
			dosend.nstop = nstop;
			dosend.max = max;
			dosend.suma = 0;
			i = 0;
			while(i < wndil)
			{
				dosend.suma += wnd[i].suma;
				i++;
			}
			
			i=0;
			max = 0;
			suma_prawo = 0;
			while(i <= wndil-1)
			{
				suma_prawo += wnd[i].max_prawo;

				if (suma_prawo > max) max = suma_prawo;
				
				suma_prawo -= wnd[i].max_prawo;
				suma_prawo += wnd[i].suma;
				i++;
			}
			dosend.max_prawo = max;

			suma_lewo = 0;
			max = 0;
			int32_t j = wndil-1;
			while(j>=0)
			{
				suma_lewo += wnd[j].max_lewo;

				if (suma_lewo > max) max = suma_lewo;
				
				suma_lewo -= wnd[j].max_lewo;
				suma_lewo += wnd[j].suma;
				j--;
			}
			
			dosend.max_lewo = max;
			
#ifdef __DEB
			deb << "dosend" << endl << "n: " << dosend.nstart << " " << dosend.nstop << endl;
			deb << "suma: " << dosend.suma << endl;
			deb << "prawo: " << dosend.max_prawo << endl;
			deb << "lewo: " << dosend.max_lewo << endl;
			deb << "max: " << dosend.max << endl << endl;
#endif			
			
		if (!nasz_proces)
		{
			WYNIKI_PROCESOW wp[ilosc_procesow];
			wp[0] = dosend;
			
			i = 1;
			while(i < ilosc_procesow)
			{
				Receive(i);
				wp[i].suma = GetLL(i);
				wp[i].max_prawo = GetLL(i);
				wp[i].max_lewo = GetLL(i);
				wp[i].max = GetLL(i);
				wp[i].nstart = GetInt(i);
				wp[i].nstop = GetInt(i);
				i++;
			}
			
#ifdef __DEB
			i = 0;
			while(i < ilosc_procesow)
			{
				deb << "Proces: " << i << endl;
				deb << "n " << wp[i].nstart << " " << wp[i].nstop << endl;
				deb << "Suma: " << wp[i].suma<< endl;
				deb << "Prawo: " << wp[i].max_prawo<< endl;
				deb << "Lewo: " << wp[i].max_lewo<< endl;
				deb << "MAX: " << wp[i].max<< endl;
				i++;
			}
#endif

			int64_t max = 0;
			int64_t suma_prawo = 0;
			int64_t suma_lewo = 0;
			int32_t i = 0;
			while(i < ilosc_procesow-1)
			{
				suma_prawo += wp[i].max_prawo;
				
#ifdef __DEB
				deb << "suma_prawo+max_prawo[" << i << "]: " << suma_prawo << endl;
#endif
				
				suma_lewo = 0;
				int64_t suma;
				int32_t j = ilosc_procesow-1;
				while(j>i)
				{
					suma_lewo += wp[j].max_lewo;
#ifdef __DEB
				deb << "		suma_lewo+max_lewo[" << j << "]: " << suma_lewo << endl;
#endif
					suma = suma_lewo + suma_prawo;
					if (suma > max) 
					{
						max = suma;
#ifdef __DEB
				deb << " ** nowe max: " << suma << endl;
#endif
					}

					suma_lewo -= wp[j].max_lewo;
					suma_lewo += wp[j].suma;
					j--;
				}
				if (i == 0)
				{
					suma_lewo += wp[0].max_lewo;
					if (suma_lewo > max) 
					{
						max = suma_lewo;
		#ifdef __DEB
				deb << " ** nowe max: " << max << endl;
		#endif
					}
				}

				suma_prawo -= wp[i].max_prawo;
				suma_prawo += wp[i].suma;
				
				i++;
			}
			
			//jeszcze ekstra tylko dla sumy w prawo i tylko dla sumy w lewo
			suma_prawo += wp[i].max_prawo;
			if (suma_prawo > max) 
			{
				max = suma_prawo;
#ifdef __DEB
		deb << " ** nowe max: " << max << endl;
#endif
			}
			
			
//max = 0;
			//do tej pory sprawdzialiśmy przypadki pomiędzy zestawami, ale nie przypadki, kiedy wynik mógł być w jednym zestawie
			//a teraz trzeba przetestować co by było, gdyby wynik znajdował się dokładnie w jednym z zestawów
			i = 0;
			while(i < ilosc_procesow)
			{
				int64_t suma = 0;
				int32_t j = 0;
				while(j < ilosc_procesow)
				{
					if (j != i)
					{
						suma += wp[j].suma;
					}
					else
					{
						suma += wp[j].max;
					}
					j++;
				}
				if (suma > max)
				{
					max = suma;
					#ifdef __DEB
									deb << " ** nowe max: " << suma << " dla: " << i << endl;
					#endif
				}
				i++;
			}				

			cout << max << endl;
		}
		else
		{
			PutLL(0, dosend.suma);
			PutLL(0, dosend.max_prawo);
			PutLL(0, dosend.max_lewo);
			PutLL(0, dosend.max);
			PutInt(0, nstart);
			PutInt(0, nstop);
			Send(0);
		}
		delete[] wnd;
		delete[] p_max_prawo;
		delete[] p_max_lewo;
	}
	return 0;
}