Ta định nghĩa block là một mảng mà tất cả các phần tử đều bằng nhau và bằng đúng độ dài của mảng đó.

Ví dụ:

[3, 3, 3], [1], [4, 4, 4, 4] là những blocks.

[1, 1, 1] and [2, 3, 3] không phải blocks.

Một mảng được gọi là neat nếu nó có thể được tạo thành bằng cách nối lại một số (có thể bằng 0) các block bất kỳ. Chú ý rằng mảng rỗng luôn là neat.

Bạn được cho một mảng a gồm n số nguyên. Hãy tìm độ dài lớn nhất của một dãy con neat của mảng a.

Input:

Dòng 1: số nguyên n (1 ≤ n ≤ 2·10⁵) — độ dài mảng.

Dòng 2: n số nguyên a₁, a₂, …, aₙ (1 ≤ ai ≤ n).

Đảm bảo rằng tổng n của tất cả test case không vượt quá 2·10⁵.

Output:

In ra một số nguyên — độ dài lớn nhất của một dãy con neat chọn được từ a.

Example

Input

10
2 3 3 1 2 3 5 1 1 7

Output

5

Đề
Ta có một lưới 2 × n, mỗi ô chứa số nguyên từ 1 đến 2n.

Với mỗi cặp số nguyên l, r (1 ≤ l ≤ r ≤ 2n), ta xây dựng một bảng nhị phân b cỡ 2 × n như sau:

b[i][j] = 1 nếu l ≤ a[i][j] ≤ r

b[i][j] = 0 ngược lại

Ta quan tâm xem trong bảng b có tồn tại đường đi "xuống–phải" chỉ đi qua các ô có giá trị 1, bắt đầu từ ô (1,1) (hàng 1, cột 1) đến ô (2,n) (hàng 2, cột n) hay không.

Đường đi "xuống–phải" nghĩa là mỗi bước hoặc:

đi sang phải (i, j) → (i, j+1) hoặc

đi xuống (i, j) → (i+1, j).

Yêu cầu: Đếm số cặp (l, r) (1 ≤ l ≤ r ≤ 2n) sao cho trong bảng f(l, r) tồn tại đường đi như trên.

Input:

Dòng 1: n (2 ≤ n ≤ 2·10⁵).

Dòng 2: n số: hàng 1.

Dòng 3: n số: hàng 2.

Output: Với mỗi test, in ra 1 số: số cặp (l, r) thỏa mãn.

INPUT

6
6 6 5 7 9 12
1 4 2 8 5 6

OUTPUT

25

INPUT

 5

 2 2 5 9 5

OUTPUT

 4

INPUT

6
5 9 8 7 10 2
1 2
1 6
2 5
3 5
2 4

OUTPUT

21