Trung thu là thời điểm diễn ra kì thi chọn ĐTQG của thành phố Đà Nẵng. Kì thi diễn ra trong \(2\) ngày, mỗi ngày thí sinh có thể kiếm được tối đa \(20\) điểm. Bé Thu có một người anh tham dự kì thi này. Để thử thách khả năng lập trình của bé Thu, người anh cho bé \(2\) danh sách \(a_1, a_2, ..., a_n\) và \(b_1, b_2, ..., b_n\) lần lượt là điểm của các thí sinh trong ngày \(1\) và \(2\) (với \(a_i\) là điểm ngày \(1\) của thí sinh thứ \(i,\) \(b_i\) là điểm ngày \(2\) của thí sinh thứ \(i\)) và cần tìm thủ khoa của kì thi.

Vì bé Thu chỉ mới học lập trình cách đây không lâu, bạn hãy giúp bé Thu in ra chỉ số của người được thủ khoa (người có tổng điểm \(2\) ngày cao nhất) trong kì thi này nhé. Nếu có nhiều hơn \(1\) thủ khoa, hãy in ra người có chỉ số thấp nhất.

Input

• Dòng đầu gồm số nguyên dương \(n (n \leq 2 * 10^5)\)
• Dòng thứ \(2\) gồm \(n\) số nguyên không âm \(a_1, a_2, ..., a_n (a_i \leq 20)\)
• Dòng thứ \(3\) gồm \(n\) số nguyên không âm \(b_1, b_2, ..., b_n (b_i \leq 20)\)

Output

• In ra chỉ số của người được thủ khoa trong kì thi này. Nếu có nhiều hơn \(1\) thủ khoa, hãy in ra người có chỉ số thấp nhất.

Example 1

Input

5
1 1 1 1 1
2 3 2 2 3

Output

2

Giải thích

• Người thứ \(2\) và \(5\) đều cùng có điểm số tổng \(2\) ngày là \(1 + 3 = 4,\) nhưng người thứ \(2\) có chỉ số nhỏ hơn \((2 < 5)\) nên in ra \(2.\)

Example 2

Input

6
11 12 17 18 15 9
5 6 1 4 11 20

Output

6

Trung thu đã gần đến rồi nhưng Hùng vẫn chưa có người đi chơi chung vì vậy năm nay cậu phải ở nhà cùng với gia đình. Quyết không để buồn chán khi phải một mình, cậu quyết định làm một chiếc bánh nhiều tầng siêu to khủng lồ để cùng gia đình ăn. Chiếc bánh cậu dự định làm gồm \(n\) tầng và phải trải qua \(n\) công đoạn để làm ra:

• Ở công đoạn thứ \(i\), Hùng sẽ làm thêm \(1\) tầng bánh nữa sau đó sẽ phủ sốt dâu tây lên \(a_i\) tầng bánh trên cùng

Sau khi đã hoàn thành được chiếc bánh, Hùng lại quên mất bản thân đã phủ sốt dâu tây lên những tầng nào thế nên cậu đành nhờ mọi người kiểm tra từng tầng của bánh. Hãy giúp Hùng biết được những tầng nào được phủ sốt dâu tây và không.

Input

• Dòng đầu tiên chứa 1 số nguyên dương \(n(1 \leq n \leq 2.10^5)\)
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_i(1 \leq a_i \leq n )\) là số lượng tầng được phủ sốt dâu tây.

Output

• Với chiếc bánh nếu tầng thứ \(i\) \((1 \leq i \leq n)\) được phủ sốt dâu thì in ra \(1,\) ngược lại in ra \(0\)

Example 1

Input

6
0 3 0 0 1 3

Output

1 1 0 1 1 1 

Giải thích

Với chiếc bánh đầu tiên (hồng là sốt dâu tây) các công đoạn là

Sau khi Hùng đã làm xong cho bản thân một chiếc bánh dâu tây siêu ngon, anh ấy quyết định cắt chiếc bánh ra làm nhiều phần. Với mỗi lần cắt bánh Hùng sẽ chọn ra \(1\) miếng bánh (ban đầu cả chiếc bánh là \(1\) miếng) có trọng lượng \(w > 2\) và cắt nó ra thành 2 phần bánh nhỏ hơn có trọng số lần lượt là \(\lfloor\frac{w}{2}\rfloor\) và \(\lceil\frac{w}{2}\rceil\) (\(\lfloor a \rfloor\) và \(\lceil a \rceil\) lần lượt là làm tròn xuống và làm tròn lên).

Sau khi cắt được chiếc bánh ra thành \(n\) miếng bánh Hùng có được trọng lượng của từng miếng bánh nhưng lại quên mất trọng lượng ban đầu của chiếc bánh (vì làm tròn) nên Hùng không biết mình có làm tròn đúng hay không vậy. Hãy giúp Hùng kiểm tra xem có tồn tại chiếc bánh nào có trọng lượng \(x\) mà sau khi cắt thành \(n\) miếng bánh thì trọng lượng của chúng đúng bằng trọng lượng của những miếng bánh mà Hùng đã tính. Nếu có thì in ra \(YES\) ngược lại in ra \(NO\).

Input

• Dòng đầu tiên chứa \(1\) số nguyên dương \(n(1 \leq n \leq 2.10^5)\)
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_i(1 \leq a_i \leq 10^6)\) là trọng lượng của các miếng bánh sau khi được cắt ra.

Dữ liệu đầu vào đảm bảo \(a_1 + a_2 + ... + a_n \leq 10^6\)

Output

• \(1\) Dòng duy nhất là kết quả của bài toán.

Example 1

Input

3
2 3 1

Output

YES

Giải thích

• Tồn tại chiếc bánh có trọng lượng ban đầu là \(6\). Lần lượt thực hiện các thao tác cắt chiếc bánh ra thành \((3, 3)\) tiếp theo cắt thành \((1, 2, 3)\).

Example 2

Input

2
869 541

Output

NO

Hùng được cho một hình đa giác đều \(n\) \((3 \leq n \leq 200000)\) cạnh. Lấy \(1\) cạnh bất kì mang chỉ số \(1\) và các cạnh tiếp theo được đánh số lần lượt là \(2, 3, ..., n\) theo chiều kim đồng hồ. Trên cạnh thứ \(i\) của hình đa giác đều sẽ có \(ai (1 \leq a_i \leq 2 * 10^9)\) điểm. Các điểm này sẽ được đặt trên cạnh sao cho cạnh \(i\) được chia thành \(a_i + 1\) đoạn liên tiếp có độ dài bằng nhau

Ví dụ, bạn có một đa giác đều có \(4\) cạnh với cạnh trên cùng mang chỉ số \(1\) và có mảng \(a = [2, 1, 3, 5]\) thì đa giác sẽ có dạng như sau.

Mỗi tam giác cô đơn bao gồm \(3\) điểm riêng biệt (không nhất thiết phải từ các cạnh khác nhau) là đỉnh của nó. Mỗi điểm chỉ có thể làm đỉnh của tối đa \(1\) tam giác cô đơn và tam giác ấy chỉ được gọi là cô đơn nếu không có bất kì tam giác nào giao với nó. Hãy đếm số lượng tam giác cô đơn lớn nhất có thể

Input

• Dòng đầu tiên gồm \(1\) số nguyên dương \(n (3 \leq n \leq 200000)\) là số lượng cạnh của đa giác đều
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_i\) \((1 \leq a_i \leq 2 * 10^9)\)

Output

• \(1\) dòng duy nhất là kết quả của bài toán.

Example 1

Input

4
3 1 4 6

Output

4

Giải thích