Trên mặt phẳng lấy \(n\) điểm \(a_1,a_2,....a_n\) sao cho không ba điểm nào thẳng hàng. Hỏi có ít nhất bao nhiêu đường thẳng \(a_ia_j\) với \(i,j \in {1,2,..,n}\) và \(i \neq j\) cắt đường thẳng \(A_1A_n\)?

Input

• Một dòng duy nhất chứa số nguyên dương \(n\) với \(n\) chẵn - là số lượng điểm \((2 \leq n \leq 10^9)\).

Output

• In ra một số nguyên duy nhất là kết quả bài toán.

Example

10

40

Cho \(n\) món hàng được đưa ra theo thứ tự và \(k\) xe tải. Mỗi món hàng khi đưa ra đều được đưa lên xe tải, mỗi xe tải có một tải trọng \(w\) là khối lượng có thể chịu được. Cho khối lượng \(a[i]\) của các món hàng được đưa ra theo thứ tự, tính \(w\) bé nhất có thể sao cho sử dụng không quá \(k\) xe tải.

Input

• Dòng đầu tiên là \(2\) số \(n\) và \(k\) \((1 \le k \le n \le 2 \times 10^5)\).
• Dòng thứ hai là \(n\) số \(a[i] (1 \le a[i] \le 10^9)\).

Output

• Chính xác \(1\) số là số \(w\) cần tìm.

5 2
3 2 4 5 1

9

Mỗi buổi sáng khi thức giấc, thầy quản sinh luôn đi bộ từ nhà mình đến ký túc xá (KTX) nhà trường để đánh thức các em học sinh dậy chuẩn bị cho việc đi học. Từ nhà đến KTX có N vị trí được nối với nhau bởi M con đường hai chiều. Mỗi con đường có độ dài xác định. Nhà của thầy giáo quản sinh ở vị trí 1 còn khu (KTX) ở vị trí N. Không có hai vị trí nào được nối với nhau bởi nhiều hơn một con đường và hệ thống đường đi này đảm bảo sự đi lại giữa hai vị trí bất kỳ. Thầy giáo luôn đi trên các con đường này và khi đi, thầy luôn chọn cho mình hành trình ngắn nhất (tổng độ dài các con đường đi qua là nhỏ nhất).
Các học sinh nghịch ngợm không muốn bị đánh thức sớm nên chúng quyết định kéo dài hành trình của thầy giáo trong mỗi buổi sáng bằng cách xây dựng các chướng ngại vật trên đúng một con đường trong số các con đường đã có sao cho việc đi trên con đường này (do phải vòng qua các chướng ngại vật) sẽ có độ dài gấp đôi độ dài ban đầu của nó.
Hãy giúp các học trò nghịch ngợm chọn ra một con đường để xây các chướng ngại vật sao cho hành trình đi đến KTX của thầy giáo là dài nhất có thể.

Input

Dòng đầu ghi hai số nguyên dương N,M (1≤N≤100,1≤M≤10000)
M dòng tiếp theo, dòng thứ i mô tả một con đường gồm 3 số \(A_i\),\(B_i\),\(L_i\) thể hiện có một con đường nối \(A_i\) với \(B_i\) có độ dài \(L_i\) (1≤\(A_i\),\(B_i\)≤n,1≤\(L_i\)≤\(10^6\)).

Output

• Độ tăng lớn nhất hành trình của thầy giáo sau khi các học sinh xây dựng các chướng ngại vật trên một con đường.

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

2

Giải thích:

Hành trình ban đầu của thầy giáo là 1-3-4-5 có tổng độ dài là 1+3+2=6.
Sau khi tăng độ dài đường 3-4 lên gấp đôi (từ 3 thành 6) thì hành trình của thầy là 1-3-5 có độ dài 1+7=8. So với độ dài lúc đầu thì tăng 8-6=2

Có một lưới một chiều có độ dài là n. Ô thứ i của lưới chứa một ký tự s_i, đó có thể là '<' hoặc '>'.
Khi một quả pinball được đặt lên một ô, nó sẽ di chuyển theo các quy tắc sau:
Nếu quả pinball đang ở ô thứ i và s_i là '<', thì quả pinball sẽ di chuyển sang ô bên trái sau một giây. Nếu s_i là '>', nó sẽ di chuyển sang ô bên phải với thời gian là 1 giây.
Sau khi quả pinball di chuyển, ký tự s_i sẽ bị đảo ngược (nghĩa là nếu s_i ban đầu là '<', nó sẽ trở thành '>', và ngược lại).
Quả pinball sẽ dừng lại khi nó rời khỏi lưới từ biên bên trái hoặc từ biên bên phải.
Người ta thả vào ô thứ p của lưới một viên Pinball, hãy tính xem mất bao nhiêu giây để quả Pinball rời khỏi lưới. Có thể chứng minh rằng quả pinball sẽ luôn rời khỏi lưới trong một số bước hữu hạn.

Input

• Dòng đầu tiên ghi số nguyên n,p (1≤p≤n≤2*\(10^5\)) là số bộ test
• Dòng thứ hai chứa một xâu ký tự, trong đó mỗi ký tự chỉ là '<' hoặc '>'.

Output

• Đưa ra thời gian để Pinball lăn ra khỏi lưới.

3 2
><<

6

Giải thích:

Ràng buộc:

Subtask1: 60% test n ≤1000
Subtask2: 40% test còn lại không có ràng buộc gì.