問題文

数直線として表すことのできる街に N 人が暮らしており、i 番目の人は座標 x_i に住んでいます。同じ座標に 2 人以上住んでいることはありません。

座標 x に住む人と、座標 y に住む人が交流するのに必要なコストは |x-y| です。

この街全体の交流コストは、N のうち全ての 2 人の組み合わせ 1 \leq i < j \leq N が交流するのにかかるコストの和として計算されます。

この交流コストを出力してください。

制約

• 2 \leq N \leq 10^5
• 0 \leq |x_i| \leq 10^8
• x_i は全て異なる
• 入力は全て整数である

入力例 1

2
-2 3

出力例 1

5

-2 と 3 に住む人同士のコストは 5 です。

入力例 2

3
10 1 5

出力例 2

18

10 と 1 に住む人同士のコストは 9 です。

10 と 5 に住む人同士のコストは 5 です。

1 と 5 に住む人同士のコストは 4 です。

よって、街の交流コストは 18 です。

問題文

英小文字から成る文字列 S が与えられます。

これは code のように、先頭の文字がその文字列においてアルファベット順で最小となる文字列を1つ以上連結してできたものです。

元となるそれぞれの文字列には、先頭と同じ文字が複数含まれていたことはありません。

S は最小で何個の文字列を繋げてできた可能性があるでしょうか。

制約

• 1 \leq |S| \leq 10^5
• S は英小文字から成る

入力例 1

codethanksfes

出力例 1

2

例えば codeth と anksfes を連結するとできます。

入力例 2

atcoder

出力例 2

1

atcoder は条件を満たします。

入力例 3

aaa

出力例 3

3

問題文

1 以上 T 以下の整数を、各 i は 0 個以上 a_{i} 個以下の範囲で、好きな個数黒板に書くことができます。

書かれている整数に対して次の操作を繰り返して、ただ 1 つの整数が黒板に書かれているようにできるような整数の書き方は何通りあるでしょうか。

• 黒板に書かれている整数のうち、2 つ以上ある整数 X を 2 つ消して、黒板に X+1 を 1 つ書く

答えは非常に大きくなることがあるので、1000000007 で割った余りを計算してください。

ただし 2 つの書き方が異なるとは、それぞれの書き方において操作を始める前に黒板に書かれている個数が異なるような整数が存在する場合を表します。

制約

• 1 \leq T \leq 300
• 0 \leq a_i \leq 300
• 入力は全て整数である

入力例 1

2
1 1

出力例 1

2

1 を 1 つ書くか、2 を 1 つ書く方法が条件を満たします。

入力例 2

3
2 1 1

出力例 2

6

入力例 3

8
300 300 300 300 300 300 300 300

出力例 3

220439161

問題文

高橋君は、N 頂点から成る根付き木上で、M 枚のコインを使って以下の操作をちょうど K 回行おうとしています。

この木は、頂点 i の親が p_i であるものとして与えられます。p_i = 0 である頂点が根です。

各操作では、

• 根にコインが置かれていない場合に、根に新しいコインを置く

もしくは

• コインの置かれている頂点を 1 つ選んで、コインの置かれていない子のどれかにコインを移動する

のどちらかを行うことができます。

K 回の操作のあと、M枚 のコイン全てが木のどこかに置かれていなければなりません。

1 枚目に根に置いたコイン, 2 枚目に根に置いたコイン, ..., M 枚目に根に置いたコイン の置かれている頂点を v_1, v_2, ..., v_M とします。

高橋君は、この列 v_1, v_2, ..., v_M のうち、辞書順で最小であるものが知りたくなりました。

高橋君のためにこの列を求めてあげてください。

列 u_1, u_2, ..., u_M が 列 v_1, v_2, ..., v_M より辞書順で小さいとは、u_i < v_i かつ 、全ての j < i で u_j = v_j が成り立つような 1 \leq i \leq M が存在する場合を言います。

ただし、ちょうど K 回の操作を行えない場合や、M 枚のコインを木に置けない場合は、-1 を出力してください。

制約

• 1 \leq M \leq N \leq 300
• 0 \leq K \leq 10^5
• 0 \leq p_i \leq N
• p_i = 0 となる i はただ 1 つ存在する
• (i, p_i) に辺を張ってできるグラフは木を成す
• 入力は全て整数である

入力例 1

3 2 4
2 0 2

出力例 1

1 3

次ののように操作を行うことで \{1, 3\} の列を作ることができ、これより辞書順で小さい列を作ることはできません。

• 1 枚目のコインを頂点 2 に置く

• 1 枚目のコインを頂点 2 から 1 に動かす

• 2 枚目のコインを頂点 2 に置く

• 2 枚目のコインを頂点 2 から 3 に動かす

上の画像では、1 枚目のコインを赤、2 枚目のコインを青で表しています。

入力例 2

3 2 5
2 0 2

出力例 2

-1

5 回の操作を行うことが出来ないので、 -1 を出力してください。

問題文

高橋君は、初めに N 枚のカードの表に 1 から N の整数を 1 つずつ書いた後、裏返してシャッフルし、また 1 から N の整数を 1 つずつ書きました。

1 \leq i \leq N 枚目のカードには、表に a_i が、裏にb_i が書かれています。

この N 枚のカードを、それぞれ好きな面を上に向けて置き、見えている整数の和を最大にしようと考えました。

しかしこのままでは高橋君には簡単すぎます。

高橋君は、見えている整数の種類が少なすぎると悲しいので、K 種類以上の整数が見えるという条件のもとで和の最大値を求めることにしました。

高橋君のためにこの値を計算してあげてください。

制約

• 1 \leq K \leq N \leq 5000
• 1 \leq a_i, b_i \leq N
• a_1, a_2, ..., a_N には 1, 2, ..., N が 1 度ずつ現れる。
• b_1, b_2, ..., b_N には 1, 2, ..., N が 1 度ずつ現れる。
• 入力は全て整数である

入力例 1

2 2
2 1
1 2

出力例 1

3

表裏が \{1, 2\} のカードと \{2, 1\} のカードがあります。

両方を表にするか、両方を裏にすることで 2 つの整数が見えるようにでき、和は 3 です。

入力例 2

2 1
2 1
1 2

出力例 2

4

表裏が \{1, 2\} のカードと \{2, 1\} のカードがあります。

両方を 2 の面を表にしてよく、和は 4 が最大です。

入力例 3

3 2
2 3 1
1 3 2

出力例 3

7

問題文

整数が 1 つずつ書かれたカードが N 枚積んであり、上から i 枚目には a_{i} が書かれています。

AliceとBobはこのカードを使ってゲームを行うことにしました。

2 人はAliceから始めて交互に、残っているカードを上から 1 枚以上好きなだけ取り、この時取った整数の和を書き出します。

カードが無くなるとこのゲームのスコアを、書き出された整数を用いて計算します。

書き出された整数の個数を K 個とした時、小さい方から (K+1)/2 以上の最小の整数 番目の値がこのゲームのスコアです。

2 人はカードに書かれている数を事前に知っています。Aliceはゲームのスコアを出来るだけ大きく、Bobは小さくしたいです。

2 人がそれぞれ最善に振る舞った時、このゲームのスコアはいくつになるでしょうか。

制約

• 1 \leq N \leq 1000
• 0 \leq |a_i| \leq 10^9
• 入力は全て整数である

入力例 1

2
1 -1

出力例 1

1

Aliceが初めに \{1, -1\} を取ると、書かれる整数は \{0\} で、スコアは 0 になります。 Aliceが初めに \{1\} を取ると、Bobは \{-1\} を取ることになり、書かれる整数は \{1, -1\} で、スコアは 1 になります。

よってAliceにとっては \{1\} を取る方が良く、スコアは 1 となります。

入力例 2

3
3 1 4

出力例 2

8