Ảo thuật gia trong một tiết mục của mình trình ra hai mảng \(S\) và \(T\) cùng có độ dài \(n\), chứa các số nguyên dương không vượt quá \(10^9\).

Sau đó, ông mời khán giả chọn ra một đoạn bắt đầu từ vị trí \(l\) và kết thúc tại vị trí \(r\) \((1 \leq l \leq r \leq n)\). Ảo thuật gia sẽ cắt ra hai đoạn \(S'\) và \(T'\) lần lượt là đoạn con của \(S\) và \(T\) từ vị trí \(l\) tới vị trí \(r\). Cuối cùng, ông ta sẽ thực hiện màn ảo thuật biến đổi đoạn \(S'\) thành \(T'\).

Tuy nhiên, vì là một ảo thuật gia tay ngang, nên công cụ của ông ta thiếu ổn định. Được biết, công cụ sẽ chỉ thực hiện biến đổi chuẩn xác 100\% khi và chỉ khi hai đoạn \(S'\) và \(T'\) thỏa mãn các điều kiện sau:

• Số lượng giá trị khác nhau trong hai đoạn \(S'\) và \(T'\) là bằng nhau
• Nếu tồn tại hai vị trí \(i \neq j\) sao cho \(S'_i = S'_j\), thì điều kiện này cũng phải được thỏa mãn sau khi biến đổi, tức \(T'_i = T'_j\).

Bạn hãy cho biết, có bao nhiêu đoạn \([l, r]\) mà khán giả có thể chọn để đảm bảo ảo thuật gia sẽ biến đổi chuẩn xác 100\%?

Input

• Dòng đầu tiên in ra số \(n\) \((n \leq 2 \cdot 10^5)\).
• Dòng thứ hai in ra \(n\) số nguyên \(S_1, S_2, \dots, S_n\) \((1 \le S_i \le 10^9)\)
• Dòng thứ ba in ra \(n\) số nguyên \(T_1, T_2, \dots, T_n\) \((1 \le T_i \le 10^9)\)

Output

• In ra một dòng duy nhất là số đoạn \([l, r]\) thỏa mãn.

Scoring

• Subtask 1 (\(10\%\)): \(n \leq 50\)
• Subtask 2 (\(15\%\)): \(n \leq 400\)
• Subtask 3 (\(25\%\)): \(n \leq 5000\)
• Subtask 4 (\(15\%\)): \(\forall i: S_i, T_i \leq 2\)
• Subtask 5 (\(20\%\)): \(\forall i: S_i, T_i \leq 64\)
• Subtask 6 (\(15\%\)): Không có điều kiện gì thêm.

Example

6
1 2 3 1 2 3
3 2 1 4 2 1

18