/*
Raul IACOBAN
problem statement may be found here:
https://www.infoarena.ro/problema/buline
In short, it is the maximal subsequence problem, but the array is circular
*/

#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<string.h>
#include<limits.h>

int* read(char *filename, size_t *N)
{
    FILE *file = fopen(filename, "r");
    if(!file)
    {
        printf("%s\n", strerror(errno));
        exit(1);
    }

    fscanf(file, "%d", N);
    int *v = calloc(*N, sizeof(int));
    for(int i=0; i<*N; i++)
    {
        int sign;
        fscanf(file, "%d %d", &v[i], &sign);
        if(sign == 0)
            sign = -1;
        v[i] *= sign;
    }

    return v;
}

void max_subseq(int *v, size_t N, int *start_, int *length_, int *sum_, int sign)
{
    int crt_sum = 0;
    int max_sum = INT_MIN;
    int max_zero = -1;
    int crt_zero = -1;
    int max_index = -1;

    for(int i=0; i<N; i++)
    {
        int elem = sign * v[i];
        if(crt_sum + elem > 0)
        {
            crt_sum += elem;
        }
        else
        {
            crt_sum = 0;
            crt_zero = i;
        }
            

        if(crt_sum > max_sum)
        {
            max_sum = crt_sum;
            max_index = i;
            max_zero = crt_zero;
        }
    }

    *start_ = max_zero + 1;;
    *length_ = max_index - max_zero;
    *sum_ = sign * max_sum;
}

int* extend(int *v, size_t N, int min_start)
{
    int Nnew = N + min_start;
    v = realloc(v, Nnew * sizeof(int));
    
    for(int i = N, j = 0; i < Nnew; i++, j++)
    {
        v[i] = v[j];
    }

    return v;
}

void print(char *filename, int a, int b, int c)
{
    FILE *file = fopen(filename, "w");
    if(!file)
    {
        printf("%s\n", strerror(errno));
        exit(1);
    }
    fprintf(file, "%d %d %d\n", a, b, c);
}

int main()
{
    int *v, *circle, start, length, sum, N_circle, dif;;
    size_t N;
    v = read("buline.in", &N);

    max_subseq(v, N, &start, &length, &sum, -1);
        //printf("%d %d %d\n", start, length, sum);
    circle = extend(v, N, start);
    dif = start + length;
    circle = circle + dif;
    N_circle = N - length;
/*
    for(int i =0; i < N_circle; i++)
    {
        printf("%d ", circle[i]);
    }
    printf("\n\n");
*/
    max_subseq(circle, N_circle, &start, &length, &sum, 1);
    //printf("%d %d %d\n", start, length, sum);

    start += dif;
    if(start >= N)
        start -= N;
    //printf("%d %d %d\n", sum, start + 1, length);
    print("buline.out", start + 1, length, sum);

    free(v);
    return 0;
}