Nizovi
Marko's math notebook has two sequences of integers written in it, both of length N. The fuzziness of these sequences is calculated by first reversing the order of the elements in the second sequence and then adding the products of elements in the same positions of the two sequences.
Image: dsadsa
For example, the fuzziness of the above two sequence of length 6 is 3\cdot2 + (-4)\cdot3 + (-3)\cdot(-1) + (-2)\cdot5 + 2\cdot0 + 0\cdot(-3) = -13. Mirko likes his pairs of sequences to be as fuzzy as possible. He decided to remove B numbers (possibly zero) from the beginning of both sequences and also E numbers (possibly zero) from the end of both sequences, so that the fuzziness is as large as possible. Write a program that finds the values of B and E for which the fuzziness is largest.
InputThe first line of input contains the integer N (1 ≤ N ≤ 2000), the length of Marko's sequences. The following two lines contain N integers each, the two sequences. All numbers in the two sequences will be between −1000 and 1000.
OutputOutput two integers B and E on the first line, such that 0 ≤ B, E < N and B+E < N. Output the resulting fuzziness on the second line. If multiple choices of B and E achieve the largest fuzziness, output any of them.
Input
Output
6
3 -4 -3 -2 2 0
-3 0 5 -1 3 2
Output
0 3
24Input
Output
5
1 1 1 1 1
2 2 2 2 2
Output
0 0
10Input
Output
5
5 -5 -5 -5 5
-5 -5 5 -5 -5
Output
2 0
75Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.