006 - Re : Jealousy_of_Parsee

時間制限 1.5 秒 / メモリ制限 128 MB / 得点 250 / x 16 /


TLE
1.5sec
MLE
128MB
得点
250
2017/01/30 入力ケースに不備があったので、訂正。

問題

橋姫がいた。

かの橋姫の名前は水橋パルスィ。

姫は、親しみを込めて『パルスィさん』と呼ばれている。

パルスィさんは、嫉妬に駆られる。

パルスィさんは、嫉妬によって力を蓄える。

パルスィさんは、嫉妬した分を幸福によって中和することでより力を蓄える。

幸福は、大人気アニメ、『魔女っ娘ヒナくるん』を見ることで溜まる。

より多くの日数をかけて中和するほど力は溜まる。

パルスィさんの一日の行動は、

  • 人里に出て嫉妬を蓄える
  • 『魔女っ娘ヒナくるん』を見て幸福を蓄える
  • のどちらかである。

    繰り返すが、パルスィさんはより多くの日数をかけて嫉妬と幸福を中和することにより、

    力が強く蓄えられる。

    さて、橋姫であるパルスィさんの側近かつ親友であるあなたには、

    パルスィさんが溜めた嫉妬と幸福の総和が『0』になる、

    つまり嫉妬と幸福が中和されている最長の区間を求めてもらいたい。

    入力形式

    入力は以下の形式で与えられる。

    N
    d1
    d2
     .
     .
    dN
    

    一行目に、判断する区間の日数 N が与えられる。

    続くN行に、パルスィさんが蓄えた嫉妬、もしくは幸福の量を示すデータ di が与えられる。

    正の値が嫉妬、負の値が幸福である。

    出力形式

    入力から得られる、嫉妬と幸福の総和が『0』になる最長の区間の長さを出力する。

    そのような区間が存在しない場合、『NA』を出力する。

    制約

    • 0 ≦ N ≦ 106
    • 0 ≦ |di| ≦ 1013

    入出力例

    入力例1

    5
    2
    5
    -8
    3
    1
    

    出力例1

    3
    

    入力例1では、2行目から4行目までの値の総和が0になるので、

    最長の区間の長さである、3を出力する。

    入力例2

    4
    1
    1
    -1
    -1
    

    出力例2

    4
    

    入力例2では、2行目から3行目までの総和が0になるが、

    1行目から4行目までの総和も0になるため、

    最長の区間の長さは4になる。

    入力例3

    10
    -89
    -89
    -89
    -89
    -89
    -89
    -89
    -89
    -89
    -89
    

    出力例3

    NA
    

    どの区間にも、総和が 0 になる区間はないため、

    『NA』を出力する。