seuOJ437 - A+B+C+D 问题

题目描述

给定一个正整数数列，询问存不存在一种划分方案，使得划分成的四个数列的和分别为 S1,S2,S3S_1,S_2,S_3 及 S4S_4。

形式化地说，是否存在 1≤p<q<r<n1\leq p<q<r<n，使得

∑i=1pAi=S1,∑i=p+1qAi=S2,∑i=q+1rAi=S3,∑i=r+1nAi=S4\sum_{i=1}^pA_i=S_1,\sum_{i=p+1}^qA_i=S_2,\sum_{i=q+1}^rA_i=S_3,\sum_{i=r+1}^nA_i=S_4

输入格式

第一行，一个正整数 n(4≤n≤105)n(4\leq n\leq 10^5)，表示数列长度。

第二行，四个正整数 S1,S2,S3,S4(1≤Si≤1014)S_1,S_2,S_3,S_4(1\leq S_i\leq 10^{14})。

第三行，nn 个正整数 Ai(1≤Ai≤109)A_i(1\leq A_i\leq 10^9)，表示数列。

输出格式

00 表示不存在这样一个划分，否则输出 11。

样例

输入样例

8
3 7 11 15
1 2 3 4 5 6 7 8

输出样例

1