Have you ever heard the quote "Everyone is a slave to something" before?

It goes like: In the grand scheme of things, most people tend to have desires that rule their life, shape their goals, and control their actions.. Whether it's the desire for money, fame, power, or even virtue; we end up doing what flows with that desire, what we originally tied ourselves to.

You might agree, you might not.. But nevertheless, dear participant, the one thing that we can know for sure at this point of time, is that $\textbf{you}$ sir (or madam), are the slave in this problem.

In this problem we have designed here, we will be providing you with an array $a$ of non-negative integers of length $n$, and will be asking you to perform a series of operations on it, fifteen precise steps, if you may; in order to test your resolve, evaluate your patience, and most importantly.. Waste your time.

Without further ado, please, perform these fifteen steps on the provided array:

1. Append the integer $0$ to the end of the array.
2. Replace every integer in the array with the maximum between it and the next number in the array (if present). In other words, set $a_i = max(a_i, a_{i+1})$
3. If the size of the array is even:
   • Split the array in half
   • Reverse each of the two sides individually
   • Merge them back into a single array in the same order
4. If the size of the array is odd:
   • Remove the longest suffix of the array that has a sum of less than or equal to $n$ (the original size of the array).
   • Jump back to step 3
5. Append these three integers to the end of the array: $[3, 2, 1]$
6. Go over the array from left to right, if $a_i$ is greater than the last element in the array, swap them.
7. Change the value of the first element in the array to be equal to $1031$.
8. Replace every integer in the array with its largest prime factor ($0$ and $1$ stay the same).
9. Sort the array in a descending order. Replace the entire array with only the unique values present in it, sorted in a descending order.
10. Replace every element in the array with its value modulo $16384$.
11. Go over the array from left to right, if the current element is equal to $6$, and the next two elements are equal to $7$ and $9$ respectively, swap the current element with the one before it in the array (if present).
12. Multiply every integer in the array by the number of its bits.
13. If the size of the array is odd, jump back to step 5.
14. If either the first element or the last element in the array is equal to zero, replace the whole array with: $[1, 2, 3, 4, 5]$
15. Output the sum of every element multiplied by its position in the array (1-indexed). In other words: $\sum\limits_{i=1}^{m} a_i * i$

The first line of input will contain an integer $n$ $(1 \le n \le 10^5)$ --- the length of the original array.

The second line will contain $n$ space-separated integers $(0 \le a_i \le n)$ --- the values of the array $a$.

Output one integer, the value described in step $15$, after carefully executing the given procedure.