stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

#define rep(i,n) for(int i=0;i<n;i++)

#define rep1(i,n) for(int i=1;i<=n;i++)

#define mp make_pair

#define F first

#define S second

#define IOS ios_base::sync_with_stdio(0); cin.tie(0)

typedef long long ll;

vector<int> g[100005];

ll q,n;

ll a[1005];

int main()

{

    //IOS;

    while(cin>>n)

    {

        map<ll,ll> m;

        vector<ll> ans;

        rep(i,n)

        {

            ll tmp;

            cin>>tmp;

            m[tmp]++;

            if(m[tmp]%2==0) ans.pb(tmp);

        }

        sort(ans.begin(),ans.end());

        if(ans.size()<2) cout<<0<<"\n";

        else cout<<ans[ans.size()-1]*ans[ans.size()-2]<<"\n";

    }

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 3.4669248965984742x):
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(),(x).end()

#define ll long long

#define vi vector<int>

#define pii pair<int,int>

#define F first

#define S second

#define pb push_back

#define forn(b) for(int i = 0; i < b; i++)

#define rforn(b) for(int i = b - 1 ;i >= 0; i--)

#define It(m) for(auto it = m.begin(); it != m.end(); it++)

#define N 500500

#define PI 3.14159265358979323846264338327950L

#define speed ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

	

const ll mod = (ll)1e9 + 7;

	

int main(){

	speed;

	int n; cin >> n;

	vector<ll> v(n);

	forn(n) {

		cin >> v[i];

	}

	sort(all(v));

	vector<ll> w {0, 0};

	int k = 0;

	for(int i = n - 2; i >= 0; i--) {

		if(v[i] == v[i + 1]) {

			w[k] = v[i];

			i--;

			k++;

			if(k == 2) break;

		}

	}

	ll res = w[0] * w[1];

	cout << res;

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define ll long long

#define N 100005

using namespace std;

int main()

{

	ll n;

	ll a[N];

	memset(a,0,sizeof(a));

	cin>>n;

	for(ll i = 0;i<n;i++)

	{

		cin>>a[i];

	}

	sort(a,a+n);

	ll x,y;

	int flag = 0; 

	ll  i ,j;

	for(i = n-1;i>=0;i--)

	{

		if(a[i]==a[i-1])

		{

			i--;

			x =a[i];

			for(j=i-1;j>=0;j--)

			{

				if(a[j]==a[j-1])

				{

					y = a[j];

					flag = 1;

					break;

				}

			}

			break;

		 } 

	}

	if(flag==0) cout<<"0"<<endl;

	else

	cout<<x*y<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8080824069422x):
#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

bool cmp(int a,int b){

    return a > b;

}

int main() {

    int n;

    cin>>n;

    int data[n];

    for(int i=0;i<n;i++)

    {

        cin>>data[i];

    }

    sort(data,data+n,cmp);

    long long a1=0,a2=0;

    for(int i=0;i<n-1;i++)

    {

        if(data[i]==data[i+1])

        {

            if(a1==0)

            {

                a1=data[i];

                i++;

            } else

            {

                a2=data[i];

                break;

            }

        }

    }

    cout<<a1*a2<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

#define rep(i,n) for(int i=0;i<n;i++)

#define rep1(i,n) for(int i=1;i<=n;i++)

#define mp make_pair

#define F first

#define S second

#define IOS ios_base::sync_with_stdio(0); cin.tie(0)

typedef long long ll;

vector<int> g[100005];

ll q,n;

ll a[1005];

int main()

{

    //IOS;

    while(cin>>n)

    {

        map<ll,ll> m;

        vector<ll> ans;

        rep(i,n)

        {

            ll tmp;

            cin>>tmp;

            m[tmp]++;

            if(m[tmp]%2==0) ans.pb(tmp);

        }

        sort(ans.begin(),ans.end());

        if(ans.size()<2) cout<<0<<"\n";

        else cout<<ans[ans.size()-1]*ans[ans.size()-2]<<"\n";

    }

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 3.543604591505491x):
#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

bool cmp(int a,int b){

    return a > b;

}

int main() {

    int n;

    cin>>n;

    int data[n];

    for(int i=0;i<n;i++)

    {

        cin>>data[i];

    }

    sort(data,data+n,cmp);

    long long a1=0,a2=0;

    for(int i=0;i<n-1;i++)

    {

        if(data[i]==data[i+1])

        {

            if(a1==0)

            {

                a1=data[i];

                i++;

            } else

            {

                a2=data[i];

                break;

            }

        }

    }

    cout<<a1*a2<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define ll long long

#define N 100005

using namespace std;

int main()

{

	ll n;

	ll a[N];

	memset(a,0,sizeof(a));

	cin>>n;

	for(ll i = 0;i<n;i++)

	{

		cin>>a[i];

	}

	sort(a,a+n);

	ll x,y;

	int flag = 0; 

	ll  i ,j;

	for(i = n-1;i>=0;i--)

	{

		if(a[i]==a[i-1])

		{

			i--;

			x =a[i];

			for(j=i-1;j>=0;j--)

			{

				if(a[j]==a[j-1])

				{

					y = a[j];

					flag = 1;

					break;

				}

			}

			break;

		 } 

	}

	if(flag==0) cout<<"0"<<endl;

	else

	cout<<x*y<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8099864234007648x):
#include <bits/stdc++.h>

using namespace std;

 

long long n, x, y, arr[100005];

 

int main () {

	cin>>n;

	

	for(int i=1; i<=n; i++){

		cin>>arr[i];

	}

	sort(arr+1, arr+n+1);

    

    for(int i=n; i>0; i--){

        if(arr[i]==arr[i-1]){

            if(x==0){

                x=arr[i];

                i--;

            }

            else{

                y=arr[i];

                break;

            }

        }

    }

    

    cout<<x*y<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

#define rep(i,n) for(int i=0;i<n;i++)

#define rep1(i,n) for(int i=1;i<=n;i++)

#define mp make_pair

#define F first

#define S second

#define IOS ios_base::sync_with_stdio(0); cin.tie(0)

typedef long long ll;

vector<int> g[100005];

ll q,n;

ll a[1005];

int main()

{

    //IOS;

    while(cin>>n)

    {

        map<ll,ll> m;

        vector<ll> ans;

        rep(i,n)

        {

            ll tmp;

            cin>>tmp;

            m[tmp]++;

            if(m[tmp]%2==0) ans.pb(tmp);

        }

        sort(ans.begin(),ans.end());

        if(ans.size()<2) cout<<0<<"\n";

        else cout<<ans[ans.size()-1]*ans[ans.size()-2]<<"\n";

    }

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 3.5473362142672453x):
#include <bits/stdc++.h>

using namespace std;

 

long long n, x, y, arr[100005];

 

int main () {

	cin>>n;

	

	for(int i=1; i<=n; i++){

		cin>>arr[i];

	}

	sort(arr+1, arr+n+1);

    

    for(int i=n; i>0; i--){

        if(arr[i]==arr[i-1]){

            if(x==0){

                x=arr[i];

                i--;

            }

            else{

                y=arr[i];

                break;

            }

        }

    }

    

    cout<<x*y<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define ll long long

#define N 100005

using namespace std;

int main()

{

	ll n;

	ll a[N];

	memset(a,0,sizeof(a));

	cin>>n;

	for(ll i = 0;i<n;i++)

	{

		cin>>a[i];

	}

	sort(a,a+n);

	ll x,y;

	int flag = 0; 

	ll  i ,j;

	for(i = n-1;i>=0;i--)

	{

		if(a[i]==a[i-1])

		{

			i--;

			x =a[i];

			for(j=i-1;j>=0;j--)

			{

				if(a[j]==a[j-1])

				{

					y = a[j];

					flag = 1;

					break;

				}

			}

			break;

		 } 

	}

	if(flag==0) cout<<"0"<<endl;

	else

	cout<<x*y<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8098593449200515x):
#include <bits/stdc++.h>

using namespace std;

 

long long N, A[100100], rct, rct2;

 

int main() {

	

    cin >> N;

    for(int i=1; i<=N; i++) {

        cin >> A[i];

    }

    

    sort(A+1, A+N+1);

 

    for (int i=N; i>=2; i--){

        if(A[i]==A[i-1]){

            rct=i;

            break;

        }

    }

    

    for (int i=rct-2; i>=2; i--){

        if(A[i]==A[i-1]){

            rct2=i;

            break;

        }

    }

    cout << A[rct]*A[rct2] << endl;

 

    

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

#define rep(i,n) for(int i=0;i<n;i++)

#define rep1(i,n) for(int i=1;i<=n;i++)

#define mp make_pair

#define F first

#define S second

#define IOS ios_base::sync_with_stdio(0); cin.tie(0)

typedef long long ll;

vector<int> g[100005];

ll q,n;

ll a[1005];

int main()

{

    //IOS;

    while(cin>>n)

    {

        map<ll,ll> m;

        vector<ll> ans;

        rep(i,n)

        {

            ll tmp;

            cin>>tmp;

            m[tmp]++;

            if(m[tmp]%2==0) ans.pb(tmp);

        }

        sort(ans.begin(),ans.end());

        if(ans.size()<2) cout<<0<<"\n";

        else cout<<ans[ans.size()-1]*ans[ans.size()-2]<<"\n";

    }

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 3.547087157097059x):
#include <bits/stdc++.h>

using namespace std;

 

long long N, A[100100], rct, rct2;

 

int main() {

	

    cin >> N;

    for(int i=1; i<=N; i++) {

        cin >> A[i];

    }

    

    sort(A+1, A+N+1);

 

    for (int i=N; i>=2; i--){

        if(A[i]==A[i-1]){

            rct=i;

            break;

        }

    }

    

    for (int i=rct-2; i>=2; i--){

        if(A[i]==A[i-1]){

            rct2=i;

            break;

        }

    }

    cout << A[rct]*A[rct2] << endl;

 

    

}
// Slower C++ solution:
  #include <map>

    #include <set>

    #include <cmath>

    #include <queue>

    #include <stack>

    #include <cstdio>

    #include <string>

    #include <vector>

    #include <cstdlib>

    #include <cstring>

    #include <sstream>

    #include <iostream>

    #include <algorithm>

    #include <functional>

    using namespace std;

    #define MX 100000

    #define ll long long

    bool cmd(ll a,ll b){

    	return a>b;

    }

    int main(){

    	ll	 N,A[110000];

    	cin>>N;

    	for(int i=0;i<N;i++){

    		scanf("%d",&A[i]);

    	}

    	sort(A,A+N,cmd);

    	int flag=0;

    	int n=0;

    	ll tp1,tp2,sum;

    	for(int i=0;i<N;i++){

    		if(A[i]==A[i+1])

    		{

    			i++;

    			n++;

    			if(n==1)

    			tp1=A[i];

    			else{

    				sum=tp1*A[i];

    				cout<<sum;

    				return 0;

    			}

    		}

    	}

    	cout<<"0";

    	return 0;

    }

// Faster C++ solution for the same problem (measured speedup: 5.333579594203474x):
#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

#include<math.h>

#define maxn 100005

const double INF=0xfffff;

using namespace std;

long long num[maxn];

int main()

{

  int n;

  long long flag1,flag2,flag3;

  int flag;

  while(scanf("%d",&n)!=EOF)

  {

  	flag1=-1;

  	flag2=-1;

  	flag=0;

    for(int i=0;i<n;i++)

    scanf("%d",&num[i]);

    sort(num,num+n);

    for(int i=n-2;i>=0;i--)

    {

    	if(num[i]==num[i+1]&&flag1==-1)

    		{

    			flag1=num[i];

    			flag2=i;

    		}

    	else if(num[i]==num[i+1]&&i<flag2-1)

    		{

    			flag=1;

    			flag3=num[i];

    			break;

    		}

    		

    }

    if(flag==0)

    	printf("0\n");

    	else

    		printf("%lld\n",flag1*flag3);

  }

   return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



// dp[i][500yen][num_1000yen] := remain ([i] is deleted)

int dp[128][1024];

int n;

int P[128];



void init() {

  for(int j = 0; j < 128; ++j) {

    for(int k = 0; k < 1024; ++k) {

      dp[j][k] = -1;

    }

  }

}



int main() {

  for(;;) {

    init();

    scanf("%d", &n);

    if( n == 0 ) break;

    for(int i = 0; i < n; ++i) {

      scanf("%d", &P[i]);

    }

    dp[0][0] = 0;

    for(int i = 0; i < n; ++i) {

      for(int j = n-1; j >= 0; --j) {

        for(int k = 1024 - 1; k >= 0; --k) {

          if( dp[j][k] == -1 ) continue;

          int n1kyen = (P[i] + 999) / 1000;

          int rem = dp[j][k] + n1kyen * 1000 - P[i];

          int next_num500yen = j + (rem >= 500 ? 1 : 0);

          int next_num1kyen  = k + n1kyen;

          int next_rem       = rem >= 500 ? rem - 500 : rem;

          int& next = dp[next_num500yen][next_num1kyen];

          next = std::max(next, next_rem);

        }

      }

    }    

    int res = (1 << 28);

    int max = -1;

    for(int j = n; j >= 0; --j) {

      for(int k = 0; k < 1024; ++k) {

        if( dp[j][k] == -1 ) continue;

        int cost = k * 1000 - 500 * j - dp[j][k];

        res = std::min(res, cost);

      }

      if( res != (1 << 28) ) {

        max = j;

        break;

      }

    }

    printf("%d %d\n", max, res);

  }



  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3071496922739212x):
#include <bits/stdc++.h>



// dp[i][500yen][num_1000yen] := remain ([i] is deleted)

int dp[128][512];

int n;

int P[128];



void init() {

  for(int j = 0; j < 128; ++j) {

    for(int k = 0; k < 512; ++k) {

      dp[j][k] = -1;

    }

  }

}



int main() {

  for(;;) {

    init();

    scanf("%d", &n);

    if( n == 0 ) break;

    for(int i = 0; i < n; ++i) {

      scanf("%d", &P[i]);

    }

    dp[0][0] = 0;

    for(int i = 0; i < n; ++i) {

      for(int j = n-1; j >= 0; --j) {

        for(int k = 512 - 1; k >= 0; --k) {

          if( dp[j][k] == -1 ) continue;

          int n1kyen = (P[i] + 999) / 1000;

          int rem = dp[j][k] + n1kyen * 1000 - P[i];

          int next_num500yen = j + (rem >= 500 ? 1 : 0);

          int next_num1kyen  = k + n1kyen;

          int next_rem       = rem >= 500 ? rem - 500 : rem;

          int& next = dp[next_num500yen][next_num1kyen];

          next = std::max(next, next_rem);

        }

      }

    }    

    int res = (1 << 28);

    int max = -1;

    for(int j = n; j >= 0; --j) {

      for(int k = 0; k < 512; ++k) {

        if( dp[j][k] == -1 ) continue;

        int cost = k * 1000 - 500 * j - dp[j][k];

        res = std::min(res, cost);

      }

      if( res != (1 << 28) ) {

        max = j;

        break;

      }

    }

    printf("%d %d\n", max, res);

  }



  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



// dp[i][500yen][num_1000yen] := remain ([i] is deleted)

int dp[128][1024];

int n;

int P[128];



void init() {

  for(int j = 0; j < 128; ++j) {

    for(int k = 0; k < 1024; ++k) {

      dp[j][k] = -1;

    }

  }

}



int main() {

  for(;;) {

    init();

    scanf("%d", &n);

    if( n == 0 ) break;

    for(int i = 0; i < n; ++i) {

      scanf("%d", &P[i]);

    }

    dp[0][0] = 0;

    for(int i = 0; i < n; ++i) {

      for(int j = n-1; j >= 0; --j) {

        for(int k = 1024 - 1; k >= 0; --k) {

          if( dp[j][k] == -1 ) continue;

          int n1kyen = (P[i] + 999) / 1000;

          int rem = dp[j][k] + n1kyen * 1000 - P[i];

          int next_num500yen = j + (rem >= 500 ? 1 : 0);

          int next_num1kyen  = k + n1kyen;

          int next_rem       = rem >= 500 ? rem - 500 : rem;

          int& next = dp[next_num500yen][next_num1kyen];

          next = std::max(next, next_rem);

        }

      }

    }    

    int res = (1 << 28);

    int max = -1;

    for(int j = n; j >= 0; --j) {

      for(int k = 0; k < 1024; ++k) {

        if( dp[j][k] == -1 ) continue;

        int cost = k * 1000 - 500 * j - dp[j][k];

        res = std::min(res, cost);

      }

      if( res != (1 << 28) ) {

        max = j;

        break;

      }

    }

    printf("%d %d\n", max, res);

  }



  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.3164386800305607x):
#include <bits/stdc++.h>



// dp[i][500yen][num_1000yen] := remain ([i] is deleted)

int dp[128][512];

int n;

int P[128];



void init() {

  for(int j = 0; j < 128; ++j) {

    for(int k = 0; k < 512; ++k) {

      dp[j][k] = -1;

    }

  }

}



int main() {

  for(;;) {

    init();

    scanf("%d", &n);

    if( n == 0 ) break;

    for(int i = 0; i < n; ++i) {

      scanf("%d", &P[i]);

    }

    dp[0][0] = 0;

    for(int i = 0; i < n; ++i) {

      for(int j = i; j >= 0; --j) {

        for(int k = 512 - 1; k >= 0; --k) {

          if( dp[j][k] == -1 ) continue;

          int n1kyen = (P[i] + 999) / 1000;

          int rem = dp[j][k] + n1kyen * 1000 - P[i];

          int next_num500yen = j + (rem >= 500 ? 1 : 0);

          int next_num1kyen  = k + n1kyen;

          int next_rem       = rem >= 500 ? rem - 500 : rem;

          int& next = dp[next_num500yen][next_num1kyen];

          next = std::max(next, next_rem);

        }

      }

    }    

    int res = (1 << 28);

    int max = -1;

    for(int j = n; j >= 0; --j) {

      for(int k = 0; k < 512; ++k) {

        if( dp[j][k] == -1 ) continue;

        int cost = k * 1000 - 500 * j - dp[j][k];

        res = std::min(res, cost);

      }

      if( res != (1 << 28) ) {

        max = j;

        break;

      }

    }

    printf("%d %d\n", max, res);

  }



  return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



// dp[i][500yen][num_1000yen] := remain ([i] is deleted)

int dp[128][1024];

int n;

int P[128];



void init() {

  for(int j = 0; j < 128; ++j) {

    for(int k = 0; k < 1024; ++k) {

      dp[j][k] = -1;

    }

  }

}



int main() {

  for(;;) {

    init();

    scanf("%d", &n);

    if( n == 0 ) break;

    for(int i = 0; i < n; ++i) {

      scanf("%d", &P[i]);

    }

    dp[0][0] = 0;

    for(int i = 0; i < n; ++i) {

      for(int j = n-1; j >= 0; --j) {

        for(int k = 1024 - 1; k >= 0; --k) {

          if( dp[j][k] == -1 ) continue;

          int n1kyen = (P[i] + 999) / 1000;

          int rem = dp[j][k] + n1kyen * 1000 - P[i];

          int next_num500yen = j + (rem >= 500 ? 1 : 0);

          int next_num1kyen  = k + n1kyen;

          int next_rem       = rem >= 500 ? rem - 500 : rem;

          int& next = dp[next_num500yen][next_num1kyen];

          next = std::max(next, next_rem);

        }

      }

    }    

    int res = (1 << 28);

    int max = -1;

    for(int j = n; j >= 0; --j) {

      for(int k = 0; k < 1024; ++k) {

        if( dp[j][k] == -1 ) continue;

        int cost = k * 1000 - 500 * j - dp[j][k];

        res = std::min(res, cost);

      }

      if( res != (1 << 28) ) {

        max = j;

        break;

      }

    }

    printf("%d %d\n", max, res);

  }



  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.343402980946722x):
#include <bits/stdc++.h>



// dp[i][500yen][num_1000yen] := remain ([i] is deleted)

int dp[128][512];

int n;

int P[128];



void init() {

  for(int j = 0; j < 128; ++j) {

    for(int k = 0; k < 512; ++k) {

      dp[j][k] = -1;

    }

  }

}



int main() {

  for(;;) {

    init();

    scanf("%d", &n);

    if( n == 0 ) break;

    for(int i = 0; i < n; ++i) {

      scanf("%d", &P[i]);

    }

    int k_max = 0;

    dp[0][0] = 0;

    for(int i = 0; i < n; ++i) {

      k_max += (P[i] + 999) / 1000;

      for(int j = i; j >= 0; --j) {

        for(int k = k_max; k >= 0; --k) {

          if( dp[j][k] == -1 ) continue;

          int n1kyen = (P[i] + 999) / 1000;

          int rem = dp[j][k] + n1kyen * 1000 - P[i];

          int next_num500yen = j + (rem >= 500 ? 1 : 0);

          int next_num1kyen  = k + n1kyen;

          int next_rem       = rem >= 500 ? rem - 500 : rem;

          int& next = dp[next_num500yen][next_num1kyen];

          next = std::max(next, next_rem);

        }

      }

    }    

    int res = (1 << 28);

    int max = -1;

    for(int j = n; j >= 0; --j) {

      for(int k = 0; k < 512; ++k) {

        if( dp[j][k] == -1 ) continue;

        int cost = k * 1000 - 500 * j - dp[j][k];

        res = std::min(res, cost);

      }

      if( res != (1 << 28) ) {

        max = j;

        break;

      }

    }

    printf("%d %d\n", max, res);

  }



  return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

#include<string>

using namespace std;

struct node

{

  int data;

  struct node*lchild;

  struct node*rchild;

};

typedef struct node;

typedef node *tree;

tree root;



void in(tree &bt,int n)

{

  if(bt)

  {

    if(n<bt->data)

      in(bt->lchild,n);

    else if(n>bt->data)

      in(bt->rchild,n);

  }

  else

  {

    bt=new node;

    bt->data=n;

    bt->lchild=NULL;

    bt->rchild=NULL;

  }

}

void out1(tree bt)

{

  if(bt)

  {

    out1(bt->lchild);

    cout<<" "<<bt->data;

    out1(bt->rchild);

  }

}

void out2(tree bt)

{

  if(bt)

  {

    cout<<" "<<bt->data;

    out2(bt->lchild);

    out2(bt->rchild);

  }

}

int main()

{

  root=NULL;

  int m;

  cin>>m;

  for(int i=1;i<=m;i++)

  {

    string zl;

    cin>>zl;

    if(zl=="insert")

    {

      int num;

      cin>>num;

      in(root,num);

    }

    else if(zl=="print")

    {

      out1(root);

      cout<<endl;

      out2(root);

      cout<<endl;

    }

  }

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.186172351410186x):
#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

#define MAXN 500000

struct node {

	int key;

	node *ch[2];

};

node tree[MAXN+5];

node *Root, *NIL, *ncnt;

void Init(){

	NIL = &tree[0];

	ncnt = &tree[1];

	Root = NIL;

}

inline node *NewNode(int val) {

	node * p = ++ncnt;

	p->key = val;

	p->ch[0] = p->ch[1] = NIL;

	return p;

}

void Insert(node * &rt, int val) {

	if(rt == NIL) {

		rt = NewNode(val);

		return ;

	}

	int d = (val >= rt->key);

	Insert(rt->ch[d], val);

}

void PreOrder(node *rt) {

	if(rt == NIL) return;

	printf(" %d", rt->key);

	PreOrder(rt->ch[0]);

	PreOrder(rt->ch[1]);

}

void InOrder(node *rt) {

	if(rt == NIL) return;

	InOrder(rt->ch[0]);

	printf(" %d", rt->key);	

	InOrder(rt->ch[1]);

}

int main() {

	int n, x;

	char op[100];

	Init();

	scanf("%d", &n);

	for(int i=0; i<n; i++){

		scanf("%s", op);

		if(op[0] == 'i') {

			scanf("%d", &x);

			Insert(Root, x);

		}

		else {

			InOrder(Root);

			puts("");

			PreOrder(Root);

			puts("");			

		}

	}

	return 0;

}