Migrated from Lutece 1515 保护果实

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A有一棵果树，但是树上的果子总是还没有成熟就被B偷偷摘走了。于是，A想买一些栅栏想把果树围起来，让B再也偷不了果子。卖栅栏的人有N块栅栏，每块栅栏长度为ai。但是，卖栅栏的人与B关系很好，他不想随便卖给A。于是，他规定，如果要买第i块栅栏，那么必须要先买第i-1块栅栏(第一块栅栏除外）。同时，A是一个不想浪费的人，他想把他买的所有栅栏都用上，并且，让栅栏围成的图形是个多边形。那么，A最少需要买多少块栅栏呢。

Input

一共有两行。

第一行一个数，表示总共的栅栏数$N(N \leq 1,000,000)$。

第二行有N个数，第i个数表示第i块栅栏的长度$a_i$ ($a_i$之和不会超过int的上界)。

Output

输出一个数，表示最少需要的栅栏数，如果无解输出-1.

Samples

3
3 4 5

3

Resources

第八届ACM趣味程序设计竞赛第三场（正式赛）