Trong chuyến dã ngoại mùa hè, ledinhbaonam và uia cùng chơi trò Thật hay thách?

Đến lượt mình, ledinhbaonam đã chọn phương án Thách và uia quyết định đưa ra một bài toán.

Nếu không giải được bài toán này, ledinhbaonam sẽ phải nhận một hình phạt bí mật do uia chuẩn bị sẵn.

uia đưa cho ledinhbaonam một dãy gồm \(N\) số nguyên: \(a_1,a_2,\ldots,a_N\)

Mỗi phần tử còn được gắn với một nhãn: \(t_i \in \{0,1,2\}\)

trong đó:

• \(t_i=0\) nếu phần tử thuộc nhóm A.
• \(t_i=1\) nếu phần tử thuộc nhóm B.
• \(t_i=2\) nếu phần tử thuộc nhóm C.

Một đoạn liên tiếp từ vị trí \(l\) đến vị trí \(r\) được gọi là cân bằng nếu số phần tử thuộc cả ba nhóm trong đoạn bằng nhau.

Nói cách khác: \(\#A=\#B=\#C\) trong đoạn \([l,r]\).

Giá trị của đoạn được định nghĩa là: \(a_l+a_{l+1}+\cdots+a_r\)

uia yêu cầu ledinhbaonam tìm giá trị lớn nhất của một đoạn cân bằng.

Nếu không tồn tại đoạn cân bằng nào, hãy in ra: KHONG

Vì không muốn nhận hình phạt nên ledinhbaonam nhờ các bạn coders giúp đỡ.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 5\cdot10^6\))

• Dòng thứ hai chứa \(N\) số nguyên \(t_1,t_2,\ldots,t_N\)

Trong đó:

• \(t_i=0\) nếu phần tử thứ \(i\) thuộc nhóm A.
• \(t_i=1\) nếu phần tử thứ \(i\) thuộc nhóm B.

• \(t_i=2\) nếu phần tử thứ \(i\) thuộc nhóm C.

• Dòng thứ ba chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\) (\(-10^{15} \le a_i \le 10^{15}\))

Output

• In ra giá trị lớn nhất của một đoạn cân bằng.

• Nếu không tồn tại đoạn cân bằng nào, in ra: KHONG

Example

9
0 1 2 0 1 2 0 1 2
5 3 2 4 1 6 2 7 3

33

5
0 0 1 1 1
2 3 4 5 6

KHONG