#include <iostream>
#include "maklib.h"
#include "message.h"

long long MIN = 0;

struct result {
  long long first, last;

  long long res;
  
  bool beg = false, end = false;
  bool mergedWithPrev = false, mergedWithNext = false;
  int prevOffset = 0, nextOffset = 0;
};

bool checkBounds(result* results, long long length) {
  for (long long i = 0; i < length; ++i) {
    if ((i > 0 && results[i].beg) || (i < length-1 && results[i].end)) {
      return true;
    }
  }

  return false;
}

void mergeWithPrevious(result* results, result* prevResults, long long index, long long nodesNo) {
  // std::cout << "instance " << index << " merging with prev" << std::endl;
  if ((index - 1 - results[index].prevOffset) >= 0) {
    if (prevResults[index-1-results[index].prevOffset].last < 0) {
      results[index].beg = false;
      return;
    } 
    results[index].res += prevResults[index-1-results[index].prevOffset].last;
    // std::cout << "prev last " << prevResults[index-1-results[index].prevOffset].last << " first " << prevResults[index-1-results[index].prevOffset].first << " res "  << prevResults[index-1-results[index].prevOffset].res << std::endl;
    if (((prevResults[index-1-results[index].prevOffset].last == prevResults[index-1-results[index].prevOffset].first) && (prevResults[index-1-results[index].prevOffset].first == prevResults[index-1-results[index].prevOffset].res)) || 
        ((prevResults[index-1-results[index].prevOffset].last == prevResults[index-1-results[index].prevOffset].first) && (prevResults[index-1-results[index].prevOffset].res == 0 ))) {
      // std::cout << "will be adding on prev" << std::endl;
      results[index].prevOffset++;
    } else {
      results[index].beg = false;
    }
  } else {
    results[index].beg = false;
  }
}


void mergeWithNext(result* results, result* prevResults, long long index, long long nodesNo) {
  // std::cout << "instance " << index << " merging with next" << std::endl;
  if ((index + 1 + results[index].nextOffset) < nodesNo) {
    if (prevResults[index+1+results[index].nextOffset].first < 0) {
      results[index].end = false;
      return;
    }
    // std::cout << "instance " << index << " merging with next " << prevResults[index+1+results[index].nextOffset].first << std::endl;
    results[index].res += prevResults[index+1+results[index].nextOffset].first;
    // std::cout << "next last " << prevResults[index+1+results[index].nextOffset].last << " first " << prevResults[index+1+results[index].nextOffset].first << " res " << prevResults[index+1+results[index].nextOffset].res << std::endl;
    if (((prevResults[index+1+results[index].nextOffset].last == prevResults[index+1+results[index].nextOffset].first) && (prevResults[index+1+results[index].nextOffset].first == prevResults[index+1+results[index].nextOffset].res)) ||
        ((prevResults[index+1+results[index].nextOffset].last == prevResults[index+1+results[index].nextOffset].first) && (prevResults[index+1+results[index].nextOffset].first == 0))) {
      // std::cout << "will be adding on next" << std::endl;
      results[index].nextOffset++;
    } else {
      results[index].end = false;
    }
  } else {
    results[index].end = false;
  }
}

void mergeResults(result* results, result* prevResults, long long nodesNo) {
  for (long long i = 0; i < NumberOfNodes(); ++i) {
    if (i > 0 && results[i].beg) {
      //merge with previous
      mergeWithPrevious(results, prevResults, i, nodesNo);
    }
    if (i < (nodesNo - 1) && results[i].end) {
      mergeWithNext(results, prevResults, i, nodesNo);
    }
  }
}

void copyResults(result* in, result* out, long long size) {
  for (long long i = 0; i < size; i++) {
    out[i] = in[i];
  }
}

int main(int argv, char** argc) {
  long long tmp, res = MIN, actual;
  tmp = res;

  long long size = Size();
  long long nodesNo = NumberOfNodes();

  if (nodesNo >= size && MyNodeId() == 0) {
    nodesNo = 1;
  }

  long long begin = (MyNodeId() * size) / nodesNo;
  long long end = ((MyNodeId() + 1) * size) / nodesNo;

  long long beginIndex = begin, endIndex = 0;

  // std::cout << MyNodeId() << " " << begin << " " << end << std::endl;

  long long tempBeginIndex = -1, prevTmp = tmp, firstVal, lastVal;

  bool first = true;
  for (long long i = begin; i < end; ++i) {
    actual = ElementAt(i+1);  
    // std::cout << MyNodeId() << " sss " << actual << " " << tmp << " " << res << std::endl;
    prevTmp += actual;
    if (tmp > 0) {
      tmp += actual;
    } else {
      tmp = actual;
      tempBeginIndex = i;
    }
    if (tmp > res) {
      res = tmp;
      beginIndex = tempBeginIndex;
      endIndex = i;
    } else {
      if (first && prevTmp > 0) {
        firstVal = prevTmp;
        first = false;
      }
    }
  }

  if (first && prevTmp == res) {
    firstVal = res;
    lastVal = res;
    first = false;
  }
  if (firstVal) {
    firstVal = prevTmp;
    // finding last
    long long lastRes = MIN;
    tmp = lastRes;
    for (long long i = end; i > begin; --i) {
      actual = ElementAt(i);  
      if (tmp > 0) {
        tmp += actual;
      } else {
        tmp = actual;
      }
      if (tmp > lastRes) {
        lastRes = tmp;
        prevTmp = tmp;
      } else {
        lastVal = tmp;
        break;
      }
    }
  }

  if (MyNodeId() > 0) {
    // std::cout << "instance " << MyNodeId() << " sending: res " << res << " beginIndex " << beginIndex << " endIndex " << endIndex << " firstVal " << firstVal << " lastVal " << lastVal << std::endl;
    PutLL(0, res);
    PutLL(0, beginIndex);
    PutLL(0, endIndex);
    PutLL(0, firstVal);
    PutLL(0, lastVal);
    Send(0);
  } else {
    result* results = new result[nodesNo];
    results[0].res = res;
    results[0].first = firstVal;
    results[0].last = lastVal;

    if (begin == beginIndex) {
      results[0].beg = true;
    }
    if (end -1 == endIndex) {
      results[0].end = true;
    }

    result bestResult = results[0];

    // std::cout << "instance 0 " << results[0].res << " " << results[0].first << " " << results[0].last << " " << beginIndex << " " << endIndex << " " << results[0].beg << " " << results[0].end << std::endl;

    long long instanceBegin, instanceEnd, instanceRes, instanceBeginIndex, instanceEndIndex, instanceFirstVal, instanceLastVal;
    for (long long instance = 1; instance < nodesNo; ++instance) {

      instanceBegin = (instance * size) / nodesNo;
      instanceEnd = ((instance + 1) * size) / nodesNo;

      Receive(instance);
      instanceRes = GetLL(instance);
      instanceBeginIndex = GetLL(instance);
      instanceEndIndex = GetLL(instance);
      instanceFirstVal = GetLL(instance);
      instanceLastVal = GetLL(instance);

      results[instance].res = instanceRes;
      results[instance].first = instanceFirstVal;
      results[instance].last = instanceLastVal;

      if (instanceBeginIndex == instanceBegin) {
        results[instance].beg = true;
      }
      if (instanceEndIndex == (instanceEnd-1)) {
        results[instance].end = true;
      }
      if (instanceRes > bestResult.res) {
        bestResult = results[instance];
      }

      // std::cout << "instance " << instance << " " << results[instance].res << " " << results[instance].first << " " << results[instance].last << " " << " " << instanceBeginIndex << " " << instanceEndIndex << " " << results[instance].beg << " " << results[instance].end << std::endl;
    }

    result* prevResults = new result[nodesNo];

    copyResults(results, prevResults, nodesNo);

    while (checkBounds(results, nodesNo)) {
      // std::cout << " while " << std::endl;
      mergeResults(results, prevResults, nodesNo);
    }

    for (long long i = 0; i < nodesNo; ++i) {
      if (results[i].res > bestResult.res) {
        bestResult = results[i];
      }
    }

    std::cout << bestResult.res << std::endl;
  }
  return 0;
}