Една низа A од N цели броеви (А[1], А[2], А[3]... А[N]) е огледална ако за секое i важи дека A[i] = A[N-i+1], каде A[i] е i-тиот елемент на низата A. Поинаку кажано, А е огледална ако при нејзиното печатење во еден ред ја отпечатиме од почеток до крај и во следниот ред ја отпечатиме од крај до почеток (во обратен редослед) во двата реда ќе биде истата низа.
Имате низа која можеби не е огледална. Сакате да ја направите огледална, со правење на следната операција, произволен број пати: Земате два соседни броја од низата и ги заменувате со нивниот збир. Забележете дека при секоја од тие операции бројот на елементи во низата ќе се намалува за еден.
Направете програма која ќе утврди кој е најмалиот број на операции кои мора да ги направите врз низата за таа да стане огледална.

Влез

Во првиот ред се наоѓа целиот број N (1 ≤ N ≤ 1 000 000).
Во следниот ред се наоѓаат N позитивни цели броеви, елементите на почетната низа. Секој од овие елементи е помал од 1 000 000 001.

Забелешка.
Во тест случаи кои носат 30% од поените важи: N ≤ 10.
Во тест случаи кои носат 60% од поените важи: N ≤ 1 000.

Излез

Во првиот ред запишете го одговорот кој се бара.

Ограничувања

Временско ограничување: 150 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
3
2 2 4

излез
1

влез
5
1 3 4 7 1

излез
1

влез
4
1 7 3 5

излез
2

Објаснување за примерите:
1. 2 2 4 -> 4 4
2. 1 3 4 7 1 -> 1 7 7 1
3. 1 7 3 5 -> 8 3 5 -> 8 8