CF501E Misha and Palindrome Degree

Misha has an array of $ n $ integers indexed by integers from $ 1 $ to $ n $ . Let's define palindrome degree of array $ a $ as the number of such index pairs $ (l,r)(1

The first line contains integer $ n $ ( $ 1

In a single line print the answer to the problem.

In the first sample test any possible pair $ (l,r) $ meets the condition. In the third sample test following pairs $ (1,3),(1,4),(1,5),(2,5) $ meet the condition.