Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P17QPROE - QUALIFY ROUND 2017 E - DÃY SỐ ĐỐI XỨNG

Cho dãy số gồm có N phần tử. Dãy số A được gọi là đối xứng nếu như A[i] = A[N-i+1] với mọi giá trị i từ 1 đến N.

Bạn được phép sử dụng thao tác gộp số, tức loại bỏ đi 2 số liền nhau trong dãy số và thay thế chúng bằng một số mới có giá trị bằng tổng của 2 số đã chọn.

Với một dãy số cho trước, hãy tính số thao tác sử dụng ít nhất để có thể biến đổi dãy số ban đầu thành một dãy số đối xứng?

Input

Dòng đầu tiên là N (N ≤ 106), số lượng phần tử trong dãy số ban đầu.

Dòng tiếp theo gồm N số nguyên A[i] (1 ≤ A[i] ≤ 109).

Output

In ra một số nguyên là đáp án của bài toán.

Example

Test 1:
Input:
3
1 2 3 Output: 1
Test 1:
Input:
4
1 4 3 2
Output:
2

Giải thích test 1: 1 2 3 à 3 3
Giải thích test 2: 1 4 3 2 à 5 3 2 à 5 5


Được gửi lên bởi:adm
Ngày:2017-04-17
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-MONKEY JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2017-07-21 21:32:04
P17QPROE: https://e16cn-ptit.blogspot.com/2017/12/p17qproe-qualify-round-2017-e-day-so-doi.html

Last edit: 2017-12-09 02:09:37
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.