Số nguyên dương ~a~ được gọi là ước nguyên dương thực sự của số nguyên ~n~ nếu ~a~ là ước của ~n~ và ~a < n~. Ví dụ số ~24~ có ~7~ ước nguyên dương thực sự là: ~1, 2, 3, 4, 6, 8, 12~.

Yêu cầu: Hãy xác định ước nguyên dương thực sự lớn nhất của ~n~.

INPUT

Gồm một dòng chứa số nguyên dương ~n~ (~2 \le n \le 10^5~).

OUTPUT

Ước nguyên dương thực sự lớn nhất của ~n~.

SAMPLE INPUT 1

4

SAMPLE OUTPUT 1

2

SAMPLE INPUT 2

7

SAMPLE OUTPUT 2

1

SAMPLE INPUT 3

24

SAMPLE OUTPUT 3

12

Cho một dãy gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~.

Yêu cầu: Đếm số cặp ~(i, j)~ đồng thời thỏa mãn:

• ~1 \le i < j \le n;~
• ~a_i + a_{i+1} + ... + a_j~ là một số chẵn.

INPUT

Dòng đầu chứa số nguyên dương ~n~ (~2 \le n \le 10^5~);

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9; i = 1, 2, ..., n~).

OUTPUT

Số lượng cặp ~(i, j)~ thỏa mãn yêu cầu của bài.

SAMPLE INPUT 1

5
1 2 3 4 5

SAMPLE OUTPUT 1

4

Giải thích: Số cặp thỏa mãn là (~1, 3~), (~1, 4~), (~2, 5~), (~3, 5~).

SAMPLE INPUT 2

4
2 5 6 4

SAMPLE OUTPUT 2

1

SUBTASKS

Dãy ~A~ gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ được gọi là dãy không giảm nếu thỏa mãn: ~a_1 \le a_2 \le ... \le a_n~.

Trung vị của dãy các số nguyên ~a_1, a_2, ..., a_n~ là phần tử xuất hiện ở vị trí ~[\frac{n+1}{2}]~ sau khi dãy đó được sắp xếp lại thành dãy không giảm.

Ví dụ: Cho dãy ~A = (2, 3, 4, 2, 8)~ sau khi sắp xếp lại thành dãy không giảm ta được dãy ~(2, 2, 3, 4, 8)~, trung vị của dãy là phần tử ~3~; dãy ~B = (3, 5, 7, 6)~ sau khi sắp xếp lại thành dãy không giảm ta được dãy ~(3, 5, 6, 7)~, trung vị của dãy là phần tử ~5~. Trung vị của dãy chỉ có một phần tử là chính phần tử đó.

Yêu cầu: Cho dãy ~A~ gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ và số nguyên ~k~. Hãy xác định trung vị lớn nhất của mọi dãy con gồm ít nhất ~k~ phần tử liên tiếp trong dãy đã cho.

INPUT

Dòng đầu chứa hai số nguyên ~n, k~ (~1 \le k \le n \le 10^5~);

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \le a_i \le n; i = 1, 2, ..., n~).

OUTPUT

In ra kết quả bài toán.

SAMPLE INPUT 1

4 2
1 3 2 4

SAMPLE OUTPUT 1

3

Giải thích:

SAMPLE INPUT 2

4 1
1 2 2 4

SAMPLE OUTPUT 2

4

SAMPLE INPUT 3

11 2
3 2 3 2 11 5 2 3 9 10 11

SAMPLE OUTPUT 3

10

SAMPLE INPUT 4

11 6
3 2 3 2 11 5 2 3 9 10 11

SAMPLE OUTPUT 4

9

SUBTASKS

Cho dãy ~a~ gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~.

Giá trị ~n~ được gọi là độ dài của dãy ~a~.

Dãy con của ~a~ là chính ~a~ hoặc là dãy nhận được từ dãy ban đầu bằng cách bỏ đi một số phần tử.

Dãy ~a~ được gọi là dãy không giảm nếu thỏa mãn: ~a_1 \le a_2 \le ... \le a_n~.

Ví dụ dãy: ~[2, 2, 4, 9, 3, 10]~ ta có một số dãy con như sau: ~[2, 2, 4, 10]~; ~[2, 9]~; ~[3, 2, 9, 10]~.

Trong đó, các dãy con ~[2, 2, 4, 10]~ và ~[2, 9, 10]~ được gọi là các dãy con không giảm.

Cho dãy ~a~ gồm ~n~ số nguyên, dãy ~b~ gồm ~m~ số nguyên. Dãy ~c~ được gọi là dãy con chung của hai dãy ~a~ và ~b~ nếu ~c~ vừa là dãy con của ~a~, vừa là dãy con của ~b~.

Ví dụ: Cho dãy ~a = (1, 2, 4, 9, 3)~ và dãy ~b = (0, 2, 15, 9)~. Dãy ~c = (2, 9)~ là một dãy con chung của hai dãy ~a~ và ~b~.

Yêu cầu: Cho hai dãy ~a~ và ~b~ chỉ chứa các số ~0~ và ~1~, dãy ~a~ có ~n~ phần tử, dãy ~b~ có ~m~ phần tử. Hãy xác định độ dài lớn nhất của dãy con chung không giảm của ~a~ và ~b~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 2 \times 10^5~) là số phần tử của dãy ~a~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~0 \le a_i \le 1~) là các phần tử của dãy ~a~.

Dòng thứ ba chứa số nguyên dương ~m~ (~1 \le m \le 2 \times 10^5~) là số phần tử của dãy ~b~.

Dòng thứ tư chứa ~m~ số nguyên dương ~b_1, b_2, ..., b_m~ (~0 \le b_i \le 1~) là các phần tử của dãy ~b~.

Dữ liệu đảm bảo luôn tồn tại dãy con chung.

OUTPUT

Độ dài lớn nhất của dãy con chung không giảm của hai dãy ~a~ và ~b~.

SAMPLE INPUT 1

7 
0 0 0 1 0 1 1
6
0 0 1 1 0 1

SAMPLE OUTPUT 1

5

Dãy con chung không giảm dài nhất là ~0, 0, 1, 1, 1~.

SAMPLE INPUT 2

10
0 0 0 1 1 1 0 1 0 0 
10
1 1 0 0 0 1 0 1 1 1

SAMPLE OUTPUT 2

7

SAMPLE INPUT 3

3
1 1 1
5
1 0 1 0 0

SAMPLE OUTPUT 3

2

SUBTASKS