Slice and dice 2

Given an array of n integers, you are asked if it’s possible to slice the array into 3 non-empty parts so that those 3 parts have the same sum.

Input

The first line of the input contains an integer n - the number of items in the array (1 ≀ n ≀ ).
The next line contains n integers separated by a space, that represent the array elements .

Output

The program should print Yes if it’s possible to slice the array in 2 places to have 3 non-empty parts of equal sums, and No otherwise.

Examples

Input
Output
5 3 2 1 3 0
Yes
4 5 -1 0 6
No

Explanation

  1. [3] [2, 1] [3, 0] β‡’ all parts sum up to 3
  1. No configuration leads to 3 parts of the same sum
Β 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue