Question
Equal Happiness Quest
In a cheerful toy store, two friends, Lily and Alex, stumbled upon N toys lined up beautifully. Each toy had a happiness value associated with it, represented by hᵢ. Excitedly, Lily decided to start picking toys from the left side of the line without skipping any. Meanwhile, Alex began his collection from the right side, also without skipping any. However, there was a catch: once one of them picked a toy, the other could no longer choose that toy.
Determined to make their happiness equal, Lily and Alex wanted to maximize the total number of toys they could collect while ensuring that the sum of happiness values from their selected toys matched. Can you help them figure out the maximum number of toys they can pick together?
Input
The first line of the input contains a single integer N.
The second line of the input contains N space-separated integers.
Constraints:
1 ≤ N ≤ 105
1 ≤ hi ≤ 104
The second line of the input contains N space-separated integers.
Constraints:
1 ≤ N ≤ 105
1 ≤ hi ≤ 104
Output
Print the maximum number of toys they can pick in total.
Example
Sample Input
5
6 1 3 4 2
Sample Output
3
Explanation
Lily can pick the toy with happiness value 6 (the first toy), while Alex can pick the toys with happiness values 4 and 2 (the last two toys). Both of them would have a total happiness of 6. Therefore, the maximum number of toys they can collectively pick is 3.
5
6 1 3 4 2
Sample Output
3
Explanation
Lily can pick the toy with happiness value 6 (the first toy), while Alex can pick the toys with happiness values 4 and 2 (the last two toys). Both of them would have a total happiness of 6. Therefore, the maximum number of toys they can collectively pick is 3.