2017/01/30 入力ケースに不備があったので、訂正。
人里に出て嫉妬を蓄える
『魔女っ娘ヒナくるん』を見て幸福を蓄える
問題
橋姫がいた。
かの橋姫の名前は水橋パルスィ。
姫は、親しみを込めて『パルスィさん』と呼ばれている。
パルスィさんは、嫉妬に駆られる。
パルスィさんは、嫉妬によって力を蓄える。
パルスィさんは、嫉妬した分を幸福によって中和することでより力を蓄える。
幸福は、大人気アニメ、『魔女っ娘ヒナくるん』を見ることで溜まる。
より多くの日数をかけて中和するほど力は溜まる。
パルスィさんの一日の行動は、
のどちらかである。
繰り返すが、パルスィさんはより多くの日数をかけて嫉妬と幸福を中和することにより、
力が強く蓄えられる。
さて、橋姫であるパルスィさんの側近かつ親友であるあなたには、
パルスィさんが溜めた嫉妬と幸福の総和が『0』になる、
つまり嫉妬と幸福が中和されている最長の区間を求めてもらいたい。
入力形式
入力は以下の形式で与えられる。
N d1 d2 . . dN
一行目に、判断する区間の日数 N が与えられる。
続くN行に、パルスィさんが蓄えた嫉妬、もしくは幸福の量を示すデータ di が与えられる。
正の値が嫉妬、負の値が幸福である。
出力形式
入力から得られる、嫉妬と幸福の総和が『0』になる最長の区間の長さを出力する。
そのような区間が存在しない場合、『NA』を出力する。
制約
- 0 ≦ N ≦ 106
- 0 ≦ |di| ≦ 1013
入出力例
入力例１
5 2 5 -8 3 1
出力例１
3
入力例１では、２行目から４行目までの値の総和が０になるので、
最長の区間の長さである、３を出力する。
入力例２
4 1 1 -1 -1
出力例２
4
入力例２では、２行目から３行目までの総和が０になるが、
１行目から４行目までの総和も０になるため、
最長の区間の長さは４になる。
入力例３
10 -89 -89 -89 -89 -89 -89 -89 -89 -89 -89
出力例３
NA
どの区間にも、総和が 0 になる区間はないため、
『NA』を出力する。