Can Three Parts Equal Sum

You are given an integer array. Determine whether it is possible to partition the array into three contiguous parts such that the sum of the elements in each part is equal.

Let \(S\) be the total sum of the elements in the array. In order for the array to be partitioned into three parts with equal sum, \(S\) must be divisible by 3. That is, let \(T = \frac{S}{3}\). You need to check if there exist two indices \(i\) and \(j\) such that the sum of the elements from the start of the array to index \(i\) is \(T\), the sum from \(i+1\) to \(j\) is also \(T\), and the remaining part sums to \(T\) as well.

Print True if such a partition exists and False otherwise.

inputFormat

The input is read from standard input and is in the following format:

n
a1 a2 a3 ... an

Where n is the number of elements in the array, and a1, a2, ..., an are the integer elements of the array.

outputFormat

Print a single line to standard output: True if the array can be partitioned into three contiguous parts with equal sum; otherwise, print False.

11
0 2 1 -6 6 -7 9 1 2 0 1

True