An array of **N** integers is given.

The ith element is called **noble** , if it can be expressed as the sum of three elements from the array having indices **smaller** than i. An element can be used more than once in the sum expression.

Find total number of noble elements in the array.

**Constraints:**

1 <= N <=10000

-100,000 <= value of array elements <= 100,000

Can someone provide an optimal solution to this question?