Divide Array into Three Contiguous Parts with Equal Sum

You are given an array of integers. Your task is to determine whether the array can be divided into three contiguous subarrays such that the sum of the elements in each subarray is equal.

Constraint: The subarrays must cover the entire array and each subarray must be non-empty.

For example, consider the array [1, 2, 3, 0, 3]. It can be partitioned into [1, 2], [3, 0], and [3] where the sum of each part is 3. However, if the array is [1, 2, 3, 4, 5, 6], no such partition exists.

The condition mathematically is given by:

$$\text{total\_sum} = \sum_{i=1}^{n} a_i, \quad \text{and if } 3 \mid \text{total\_sum}, \text{ then } \text{target} = \frac{\text{total\_sum}}{3}. $$

You need to check if the array can be segmented into exactly three contiguous parts each with sum equal to \( \text{target} \).

inputFormat

The first line contains a single integer \( n \) representing the number of elements in the array.

The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output a single line containing either True or False (without quotes) indicating whether the array can be partitioned into three contiguous parts with equal sum.

## sample

5
1 2 3 0 3

True