Trong toán học, người ta định nghĩa trung vị của một dãy số độ dài ~n~ là phần tử thứ ~\left\lfloor \dfrac{n+1}{2} \right\rfloor~ sau khi sắp xếp các số theo thứ tự không giảm. Ta định nghĩa hai dãy số tương đồng là hai dãy số có trung vị bằng nhau.

Yêu cầu: Cho một dãy ~n~ số nguyên không âm ~a_1,a_2, \ldots,a_n~; bạn hãy tính số dãy con của dãy số đã cho đồng dạng với nó. Một dãy ~b~ được gọi là dãy con của ~a~ nếu có thể thu được ~b~ bằng cách xóa đi một số phần tử ở đầu và ở cuối (Có thể không xóa số nào).

Input

Dòng đầu tiên chứa số nguyên ~n\ (1 ≤ n ≤ 10^5)~ là độ dài dãy số .

Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_1,a_2,\ldots ,a_n~ (~a_i \le 10^9~) mô tả dãy số được cho. Các số cách nhau bởi dấu cách.

Output

Một số nguyên duy nhất là số dãy con đồng dạng với dãy ban đầu.

Scoring

Sample Input 1

6
1 7 7 0 1 3

Sample Output 1

11

Sample Input 2

4
3 2 3 5

Sample Output 2

6

Notes

Trong test ví dụ một, trung vị của dãy số được cho là 1. Các dãy đồng dạng với dãy được cho là: ~[1]~, ~[1]~, ~[1, 7]~, ~[1, 3]~, ~[7, 0, 1]~, ~[0, 1, 3]~, ~[1, 7, 7, 0]~, ~[7, 7, 0, 1]~, ~[7, 0, 1, 3]~, ~[1, 7, 7, 0, 1]~, ~[1, 7, 7, 0, 1, 3]~.

Trong test ví dụ hai, trung vị của dãy số được cho là 3 (dãy sắp xếp là ~2, 3, 3, 5~, phần tử thứ ~\lfloor \frac{4+1}{2} \rfloor = 2~ là 3). Các dãy đồng dạng với dãy được cho là: ~[3]~, ~[3]~, ~[3, 5]~, ~[3, 2, 3]~, ~[2, 3, 5]~, ~[3, 2, 3, 5]~.