kh0i có một túi gồm ~n~ cây que, cây que thứ ~i~ có độ dài ~a_i~. kh0i muốn các bạn tính xem có bao nhiêu bộ BA cây QUE khác nhau thỏa mãn chúng tạo với nhau thành một tam giác cân.

Chú ý : ~(a_i,a_j,a_k)~ và ~(a_j,a_k,a_i)~ là hai bộ giống nhau.

Input

• Dòng đầu gồm một số nguyên dương ~n~ ~(3 \le n \le 10^5)~.
• Dòng thứ hai gồm một dãy ~n~ số nguyên dương ~a_1, a_2, \dots, a_{n}~ ~(1 \le a_i \le 10^9)~ là độ dài các cây que.

Output

• In ra đáp số là số bộ thỏa mãn.

Sample Input

5
1 3 2 2 2

Sample Output

7

Notes

• Các bộ thỏa mãn là các vị trí ~(1,3,4)~,~(1,3,5)~,~(1,4,5)~,~(2,3,4)~,~(2,3,5)~,~(2,4,5)~,~(3,4,5)~

Cho dãy ~a~ gồm ~n~ phần tử. Đoạn ~[l, r]~ của dãy ~a~ là dãy gồm các phần tử liên tiếp ~a_l, a_{l + 1}, \cdots, a_r~. Độ xấu của đoạn ~[l, r]~ là số lượng vị trí ~i \ (l \leq i \leq r)~ sao cho ~a_i \neq i - l + 1~. Hãy chia dãy ~a~ thành các đoạn sao cho một phần tử ~a_i~ thuộc đúng một đoạn và tổng độ xấu của các đoạn là nhỏ nhất.

Input: Vào từ file văn bản MSEQ.INP

• Dòng đầu tiên chứa số nguyên dương ~n \ (1 \leq n \leq 2 \times 10^5)~ tương ứng là độ dài dãy ~a~.
• Dòng thứ hai chứa ~n~ số nguyên dương lần lượt là ~a_1, a_2, \cdots, a_n \ (1 \leq a_i \leq n)~ tương ứng với giá trị của các phần tử thuộc dãy ~a~.

Output: Ghi ra file văn bản MSEQ.OUT

• Ghi trên một dòng duy nhất là tổng độ xấu nhỏ nhất.

Subtasks

• Subtask 1 ~(25 \%)~: ~n \leq 200~.
• Subtask 2 ~(25 \%)~: ~n \leq 3000~.
• Subtask 3 ~(25 \%)~: ~a_i \leq 200, \ \forall \ 1 \leq i \leq n~.
• Subtask 4 ~(25 \%)~: Không có ràng buộc gì thêm.

Sample Input 1

5
2 1 3 2 1

Sample Output 1

2

Cho một hoán vị ~p~ của ~n~ số nguyên dương ~1, 2, 3, \dots n~.

Ta định nghĩa một dãy đặc biệt là một dãy con liên tiếp ~[l, r]~ thỏa mãn ~p_l + p_r = max(p_l, p_{l + 1}, p_{l + 2}, \dots p_r)~. Nhiệm vụ của bạn là đếm số lượng dãy đặc biệt có trong hoán vị ~p~ cho trước.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ là độ dài của hoán vị ~(3 \leq n \leq 2 \times 10^5)~.
• Dòng tiếp theo chứa ~n~ số nguyên dương phân biệt ~a_1, a_2, \dots a_n~ ~(1 \leq a_i \leq n)~ tương ứng là hoán vị ~p~.

Output

• In ra đáp án trên một dòng duy nhất là số lượng dãy con đặc biệt trong hoán vị ~p~.

Subtasks

• Subtask 1 ~(20 \%)~: ~n \leq 10~.
• Subtask 2 ~(30 \%)~: ~n \leq 1000~.
• Subtask 3 ~(20 \%)~: ~n \leq 10000~.
• Subtask 4 ~(30 \%)~: Không có ràng buộc gì thêm.
-

Sample Input 1

5
5 4 1 3 2

Sample Output 1

1

Sample Output 2

4
1 4 3 2

Sample Output 2

1