7의 배수가 되는 연속 구간

면접 대비

시간 제한2초메모리 제한512 MB

요약

소 ID 수열에서 합이 7의 배수가 되는 가장 긴 연속 구간의 길이를 구합니다.

난이도: 보통10점 중 4점
유형: 누적 합, 해시맵
정답자: 아직 제출이 없습니다

문제

농부 존의 소 $N$ 마리가 한 줄로 서 있다. 소마다 서로 다른 정수 ID가 붙어 있어서 존은 소를 구별한다. 존은 줄에서 연속한 소 무리를 사진으로 찍으려고 하는데, 어린 시절 숫자 $1$ 부터 $6$ 까지와 얽힌 일 때문에 ID의 합이 $7$ 의 배수인 무리만 찍는다.

존이 찍을 수 있는 가장 큰 무리에 소가 몇 마리 있는지 구하라.

입력

첫째 줄에 $N$ ( $1 \le N \le 50{,}000$ )이 주어진다. 다음 $N$ 개 줄에는 소의 ID가 줄에 선 순서대로 한 줄에 하나씩 주어진다. 모든 ID는 $0$ 이상 $1{,}000{,}000$ 이하의 정수다.

출력

ID의 합이 $7$ 의 배수인 연속 구간 중 가장 긴 구간에 속한 소의 수를 출력한다. 그런 구간이 없으면 $0$ 을 출력한다.

소가 많은 구간에서는 ID의 합이 32비트 정수 범위를 넘을 수 있다. 합을 직접 더해 나간다면 C나 C++의 long long 같은 64비트 정수형을 쓰는 편이 안전하다.

힌트

예제에서는 $5+1+6+2+14 = 28$ 이 $7$ 의 배수이므로 답이 $5$ 다.

예제2

예제 1
입력
```
7
3
5
1
6
2
14
10
```
예상 출력
```
5
```
예제 2
입력
```
3
1
2
3
```
예상 출력
```
0
```