Language: C

using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using LayoutKind = System.Runtime.InteropServices.LayoutKind;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;


static class P
{
    static SegmentTree<Tuple<Tuple<int, int>, Tuple<int, int>>> segTree;
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        var p = Console.ReadLine().Split().Select(int.Parse).ToArray();
        //その中で前から見て奇数番目にあるものの中で最小と、その後の区間の奇数番目

        var IdentityElement = new Tuple<int, int>(int.MaxValue, -1);
        segTree = new SegmentTree<Tuple<Tuple<int, int>, Tuple<int, int>>>(
            p.Select((x, y) =>
            new Tuple<Tuple<int, int>, Tuple<int, int>>(
                y % 2 == 0 ? new Tuple<int, int>(x, y) : IdentityElement, 
                y % 2 == 0 ? IdentityElement : new Tuple<int, int>(x, y))
            ).ToArray(),
            new Tuple<Tuple<int, int>, Tuple<int, int>>(IdentityElement, IdentityElement),
            (x, y) => new Tuple<Tuple<int, int>, Tuple<int, int>>(x.Item1.Item1 < y.Item1.Item1 ? x.Item1 : y.Item1, x.Item2.Item1 < y.Item2.Item1 ? x.Item2 : y.Item2)
        );
        int[] res = Solve(0, n);
        Console.WriteLine(string.Join(" ", res));
    }

    static int[] Solve(int l, int r)
    {
        if (l == r) return new int[0];
        var firstPivot = l % 2 == 0 ? segTree.Query(l, r).Item1 : segTree.Query(l, r).Item2;
        var secondPivot = l % 2 == 0 ? segTree.Query(firstPivot.Item2 + 1, r).Item2 : segTree.Query(firstPivot.Item2 + 1, r).Item1;
        
        var firstSection = Solve(l, firstPivot.Item2);
        var secondSection = Solve(firstPivot.Item2 + 1, secondPivot.Item2);
        var thirdSection = Solve(secondPivot.Item2 + 1, r);
        return new int[2] { firstPivot.Item1, secondPivot.Item1 }.Concat(MergeArray(MergeArray(firstSection, secondSection), thirdSection)).ToArray();
    }

    static int[] MergeArray(int[] a, int[] b)
    {
        int aptr = 0;
        int bptr = 0;
        int[] res = new int[a.Length + b.Length];

        while (aptr < a.Length && bptr != b.Length)
        {
            if (a[aptr] < b[bptr])
            {
                res[aptr + bptr] = a[aptr];
                res[aptr + bptr + 1] = a[aptr + 1];
                aptr += 2;
            }
            else
            {
                res[aptr + bptr] = b[bptr];
                res[aptr + bptr + 1] = b[bptr + 1];
                bptr += 2;
            }
        }
        while (aptr < a.Length)
        {
            res[aptr + bptr] = a[aptr];
            res[aptr + bptr + 1] = a[aptr + 1];
            aptr += 2;
        }
        while (bptr < b.Length)
        {
            res[aptr + bptr] = b[bptr];
            res[aptr + bptr + 1] = b[bptr + 1];
            bptr += 2;
        }
        return res;
    }
}


class SegmentTree<T>
{
    public int Size { get; private set; }
    T IdentityElement;
    T[] Data;
    Func<T, T, T> Merge;
    int LeafCount;

    public SegmentTree(int size, T identityElement, Func<T, T, T> merge) : this(Enumerable.Repeat(identityElement, size).ToArray(), identityElement, merge) { }

    public SegmentTree(T[] elems, T identityElement, Func<T, T, T> merge)
    {
        Size = elems.Length;
        Merge = merge;
        IdentityElement = identityElement;
        LeafCount = 1;
        while (LeafCount < elems.Length) LeafCount <<= 1;

        Data = new T[LeafCount * 2];
        elems.CopyTo(Data, LeafCount);
        for (int i = LeafCount - 1; i >= 1; i--) Data[i] = Merge(Data[i * 2], Data[i * 2 + 1]);
    }

    public T this[int index]
    {
        get { return Data[LeafCount + index]; }
        set { Update(index, value); }
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Update(int i, T x)
    {
        i += LeafCount;
        Data[i] = x;
        while (0 < (i >>= 1)) Data[i] = Merge(Data[i * 2], Data[i * 2 + 1]);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Operate(int i, T x)
    {
        i += LeafCount;
        Data[i] = Merge(Data[i], x);
        while (0 < (i >>= 1)) Data[i] = Merge(Data[i * 2], Data[i * 2 + 1]);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public T Query(int l, int r)
    {
        l += LeafCount;
        T lRes = IdentityElement;
        r += LeafCount - 1;
        T rRes = IdentityElement;
        while (l <= r)
        {
            if (l % 2 == 1) lRes = Merge(lRes, Data[l]);
            if (r % 2 == 0) rRes = Merge(Data[r], rRes);
            l = (l + 1) / 2;
            r = (r - 1) / 2;
        }
        return Merge(lRes, rRes);
    }
}

Compiler output:
main.c:1:1: error: unknown type name 'using'
    1 | using System;
      | ^~~~~
main.c:2:1: error: unknown type name 'using'
    2 | using System.IO;
      | ^~~~~
main.c:2:13: error: expected '=', ',', ';', 'asm' or '__attribute__' before '.' token
    2 | using System.IO;
      |             ^
main.c:3:1: error: unknown type name 'using'
    3 | using System.Linq;
      | ^~~~~
main.c:3:13: error: expected '=', ',', ';', 'asm' or '__attribute__' before '.' token
    3 | using System.Linq;
      |             ^
main.c:4:1: error: unknown type name 'using'
    4 | using System.Collections;
      | ^~~~~
main.c:4:13: error: expected '=', ',', ';', 'asm' or '__attribute__' before '.' token
    4 | using System.Collections;
      |             ^
main.c:5:1: error: unknown type name 'using'
    5 | using System.Collections.Generic;
      | ^~~~~
main.c:5:13: error: expected '=', ',', ';', 'asm' or '__attribute__' before '.' token
    5 | using System.Collections.Generic;
      |             ^
main.c:6:1: error: unknown type name 'using'
    6 | using System.Text;
      | ^~~~~
main.c:6:13: error: expected '=', ',', ';', 'asm' or '__attribute__' before '.' token
    6 | using System.Text;
      |             ^
main.c:7:1: error: unknown type name 'using'
    7 | using System.Numerics;
      | ^~~~~
main.c:7:13: error: expected '=', ',', ';', 'asm' or '__attribute__' before '.' token
    7 | using System.Numerics;
      |             ^
main.c:8:1: error: unknown type name 'using'
    8 | using System.Threading.Tasks;
      | ^~~~~
main.c:8:13: error: expected '=', ',', ';', 'asm' or '__attribute__' before '.' token
    8 | using System.Threading.Tasks;
      |             ^
main.c:9:1: error: unknown type name 'using'
    9 | using System.Text.RegularExpressions;
      | ^~~~~
main.c:9:13: error: expected '=', ',', ';', 'asm' or '__attribute__' before '.' token
    9 | using System.Text.RegularExpressions;
      |             ^
main.c:10:6: error: expected ';' before 'static'
   10 | using static System.Math;
      |      ^~~~~~~
      |      ;
main.c:10:20: error: expected '=', ',', ';', 'asm' or '__attribute__' before '.' token
   10 | using static System.Math;
      |                    ^
main.c:11:1: error: unknown type name 'using'
   11 | using Debug = System.Diagnostics.Debug;
      | ^~~~~
main.c:11:21: error: request for member 'Diagnostics' in something not a structure or union
   11 | using Debug = System.Diagnostics.Debug;
      |                     ^
main.c:12:1: error: unknown type name 'using'
   12 | using LayoutKind = System.Runtime.InteropServices.LayoutKind;
      | ^~~~~
main.c:12:26: error: request for member 'Runtime' in something not a structure or union
   12 | using LayoutKind = System.Runtime.InteropServices.LayoutKind;
      |                          ^
main.c:13:1: error: unknown type name 'using'
   13 | using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
      | ^~~~~
main.c:13:33: error: request for member 'Runtime' in something not a structure or union
   13 | using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
      |                                 ^
main.c:14:1: error: unknown type name 'using'
   14 | using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
      | ^~~~~
main.c:14:35: error: request for member 'Runtime' in something not a structure or union
   14 | using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
      |                                   ^
main.c:17:8: error: unknown type name 'class'
   17 | static class P
      |        ^~~~~
main.c:18:1: error: expected '=', ',', ';', 'asm' or '__attribute__' before '{' token
   18 | {
      | ^
main.c:90:1: error: unknown type name 'class'
   90 | class SegmentTree<T>
      | ^~~~~
main.c:90:18: error: expected '=', ',', ';', 'asm' or '__attribute__' before '<' token
   90 | class SegmentTree<T>
      |                  ^