The Lead Game

To View Problem Statement Click here
Consider the following score sheet for a game with 5 rounds:

Input

The first line of the input will contain a single integer N (N ≤ 10000) indicating the number of rounds in the game. Lines 2,3,...,N+1 describe the scores of the two players in the N rounds. Line i+1 contains two integer Si and Ti, the scores of the Player 1 and 2 respectively, in round i. You may assume that 1 ≤ Si ≤ 1000 and 1 ≤ Ti ≤ 1000.

Output

Your output must consist of a single line containing two integers W and L, where W is 1 or 2 and indicates the winner and L is the maximum lead attained by the winner.

Example

Input:

5
140 82
89 134
90 110
112 106
88 90

Output:

1 58

Solution
To run the code Click Here

import java.util.*;
import java.lang.*;
import java.io.*;


public class Main {
        public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
    int n= sc.nextInt();
    int sum=0;
    int sum1=0;
    int arr_win[]= new int[n];
    int arr_diff[]=new int[n];
    for(int i= 0 ; i <n;i++) {
        int  p1 = sc.nextInt();
        int p2= sc.nextInt();
        sum += p1;
        sum1 += p2;
        if(sum>sum1) {
        arr_diff[i]= sum-sum1;
        arr_win[i]= 1;
        }
        else if(sum1>sum) {
            arr_diff[i]= sum1-sum;
            arr_win[i]= 2;
        }

        }   

int p =0;
    int max=arr_diff[0];
    for(int i = 1 ;i < n; i++) {

    if( arr_diff[i]> max) {
        max= arr_diff[i];
        p=i;

    }
    }
    System.out.println(arr_win[p]+" "+max);


    sc.close();
    }
}