SOLVE

LATER

Palindromic Sum

/

Given an array *A* of length *N*, find the number of non empty sub-arrays such that sum of all the elements in the sub-array is a palindrome. In other words, you have to find number of pairs \((i,\;j)\) such that \(\sum_{x=i}^j A_x\) is a palindrome where \((1 \le i \le j \le N)\).

**Input Format:**

First line contains an integer, *N* \((1 \le N \le 5 * 10^5)\). Second line contains *N* space separated integers, \(A_i\) \((1 \le A_i \le 2 * 10^6)\), elements of the array *A*. The sum of all the elements in the array is in the range \([1, 2 * 10^6]\).

**Output Format:**

Print an integer, number of non empty sub-arrays such that sum of all the elements in the sub-array is a palindrome.

Explanation

The 3 sub-arrays are \((10,\;1)\), *1* and *3*.

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...