入力

入力は以下の形式で標準入力から与えられる。

a b c

• 3 つの整数 a, b, c (1 ≦ a, b, c ≦ 100) が空白区切りで与えられる。

出力

a, b, c の中央値を標準出力に出力せよ。

末尾の改行を忘れないこと。

入力

入力は以下の形式で標準入力から与えられる。

s

• 圧縮する文字列 s (1 ≦ |s| ≦ 1,000) が与えられる( |s| は文字列 s の長さを表す)。
• s は英小文字から成る文字列であることが保証される。

出力

s から作られた圧縮された文字列を標準出力に出力せよ。

末尾の改行を忘れないこと。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 .. a_N

• 1 行目には、高橋くんが箱に入れる整数の個数 N ( 1 ≦ N ≦ 10^5) が与えられる。
• 2 行目には、高橋くんが箱に入れる N 個の整数が空白を区切りとして与えられる。
• 1 ≦ a_i ≦ 10^9 ( 1 ≦ i ≦ N) であることが保証される。
• i ≠ j のとき、a_i ≠ a_j であることが保証される。

出力

最大で何種類の整数が出てくるかを標準出力に出力せよ。

末尾の改行を忘れないこと。

部分点

この問題には部分点が設定されている。

• 20 点分のテストケースにおいて、1 ≦ N ≦ 3,000 を満たす。
• 別の 30 点分のテストケースにおいて、1 ≦ a_i ≦ 5*10^5 ( 1 ≦ i ≦ N) を満たす。

入出力

まず，木の頂点の数 N が標準入力に与えられる。

N

続いて，あなたのプログラムは何回か応答プログラムに質問をする．質問のフォーマットは以下のとおりである。

? a b

この質問で，a,b 間の距離が標準入力に1行で渡される。1 ≦ a, b ≦ N かつ a≠b を満たしていなければならない。

何回か質問を行った後、あなたは木の直径を当てる。木の直径を diameter とおくと、

! diameter

というフォーマットで出力する。木の直径を出力した後、あなたのプログラムは直ちに終了しなければならない。終了しなかった場合のジャッジ結果は不定である。

また、これら以外のフォーマットで出力した場合のジャッジ結果も不定である。

この問題ではテストケースごとに質問回数の上限値が設定されており、プログラムの行った質問の回数がその上限値を上回ると誤答と判定される。

正答かどうかは木の直径の出力で判断される。木の直径を特定し得ない質問しかしていない場合でも、直径が正しければ正答となる。

頂点 1 と頂点 2 の間の距離を質問し、dist という変数で結果を受け取る例をいくつかの言語について示す。

ただし、ここに書かれている方法以外で入出力を行っても良い。

出力した後に、出力をflushしなければならないことに注意せよ。flushしなかった場合、TLEとなることがある。

C

printf("? %d %d\n", 1, 2);
fflush(stdout);
scanf("%d", &dist);

C++

cout << "? " << 1 << " " << 2 << endl;
cin >> dist;

Java

System.out.printf("? %d %d\n", 1, 2);
Scanner scanner = new Scanner(System.in);
dist = scanner.nextInt();

C#

Console.WriteLine("? {0} {1}", 1, 2);
dist = int.Parse(Console.ReadLine());

D

writeln("? ", 1, " ", 2);
stdout.flush();
dist = readln.chomp.to!int;

PHP

echo "? ", 1, " ", 2, PHP_EOL;
$dist = trim(fgets(STDIN));

Python

print "? {0} {1}".format(1, 2)
sys.stdout.flush()
dist = int(raw_input())

Perl

$|=1;
print "? ", 1, " ", 2, "\n";
$dist = <>;

Ruby

print "? ", 1, " ", 2, "\n"
STDOUT.flush
dist = gets.to_i

制約

• 2 ≦ N ≦ 50
• 1 ≦ (それぞれの辺の重み) ≦ 10^6