using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("6");
WillReturn.Add("3 2 1 1 2 3");
//3 3 3 3 3 3
}
else if (InputPattern == "Input2") {
WillReturn.Add("6");
WillReturn.Add("3 1 10 3 10 2");
//3 3 10 10 10 2
}
else if (InputPattern == "Input3") {
WillReturn.Add("6");
WillReturn.Add("1 3 10 1 10 2");
//1 3 10 10 10 2
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
class RangeInfoDef
{
internal int RangeSta;
internal int RangeEnd;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
int LeafCnt = AArr.Length;
var InsLazySegmentTree = new LazySegmentTree(LeafCnt);
var RangeDict = new Dictionary<int, RangeInfoDef>();
for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
if (RangeDict.ContainsKey(AArr[I]) == false) {
RangeDict[AArr[I]] = new RangeInfoDef();
RangeDict[AArr[I]].RangeSta = I;
}
RangeDict[AArr[I]].RangeEnd = I;
}
foreach (var EachPair in RangeDict.OrderBy(pX => pX.Key)) {
InsLazySegmentTree.RangeUpdate(
EachPair.Value.RangeSta, EachPair.Value.RangeEnd, EachPair.Key, 0);
}
var AnswerList = new List<int>();
for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
int MinVal = InsLazySegmentTree.Query(I, I, 0);
AnswerList.Add(MinVal);
}
string[] AnswerArr = Array.ConvertAll(AnswerList.ToArray(), pX => pX.ToString());
Console.WriteLine(string.Join(" ", AnswerArr));
}
}
#region LazySegmentTree
// LazySegmentTreeクラス (RMQ and RUQ)
internal class LazySegmentTree
{
private int[] mTreeNodeArr;
private int UB; // 木のノードの配列のUB
private int mLeafCnt; // 葉ノードの数
private int?[] mLazyArr; // 遅延配列
// ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列
private struct RangeInfoDef
{
internal int StaInd;
internal int EndInd;
}
private RangeInfoDef[] mRangeInfo;
// コンストラクタ
internal LazySegmentTree(int pLeafCnt)
{
// 簡単のため、葉ノード数を2のべき乗に
int ArrLength = 0;
for (int I = 1; I < int.MaxValue; I *= 2) {
ArrLength += I;
mLeafCnt = I;
if (pLeafCnt < mLeafCnt) break;
}
// すべての値をint.MaxValueに
UB = ArrLength - 1;
mTreeNodeArr = new int[UB + 1];
for (int I = 0; I <= UB; I++) {
mTreeNodeArr[I] = int.MaxValue;
}
// 遅延配列を初期化
mLazyArr = new int?[UB + 1];
// ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列の作成
mRangeInfo = new RangeInfoDef[UB + 1];
for (int I = 0; I <= UB; I++) {
if (I == 0) {
RangeInfoDef WillSet1;
WillSet1.StaInd = 0;
WillSet1.EndInd = mLeafCnt - 1;
mRangeInfo[I] = WillSet1;
continue;
}
int ParentNode = DeriveParentNode(I);
RangeInfoDef ParentRangeInfo = mRangeInfo[ParentNode];
RangeInfoDef WillSet2;
int Mid = (ParentRangeInfo.StaInd + ParentRangeInfo.EndInd) / 2;
if (I % 2 == 1) { // 奇数ノードの場合
WillSet2.StaInd = ParentRangeInfo.StaInd;
WillSet2.EndInd = Mid;
}
else { // 偶数ノードの場合
WillSet2.StaInd = Mid + 1;
WillSet2.EndInd = ParentRangeInfo.EndInd;
}
mRangeInfo[I] = WillSet2;
}
}
// 親ノードの添字を取得
private int DeriveParentNode(int pTarget)
{
return (pTarget - 1) / 2;
}
// 子ノードの添字(小さいほう)を取得
private int DeriveChildNode(int pTarget)
{
return pTarget * 2 + 1;
}
// カレントノードを引数として、遅延評価を行う
void LazyEval(int pCurrNode)
{
// 遅延配列が空なら何もしない
if (mLazyArr[pCurrNode].HasValue == false) return;
// 遅延配列の値を反映する
mTreeNodeArr[pCurrNode] = mLazyArr[pCurrNode].Value;
int ChildNode1 = DeriveChildNode(pCurrNode);
int ChildNode2 = ChildNode1 + 1;
if (ChildNode1 <= UB) {
mLazyArr[ChildNode1] = mLazyArr[pCurrNode].Value;
}
if (ChildNode2 <= UB) {
mLazyArr[ChildNode2] = mLazyArr[pCurrNode].Value;
}
// 伝播が終わったので、自ノードの遅延配列を空にする
mLazyArr[pCurrNode] = null;
}
// 開始添字と終了添字とカレントノードを引数として、区間更新を行う
internal void RangeUpdate(int pSearchStaInd, int pSearchEndInd, int pUpdateVal, int pCurrNode)
{
// カレントノードの遅延評価を行う
LazyEval(pCurrNode);
int CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;
int CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;
// OverLapしてなければ、何もしない
if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd) {
return;
}
// 完全に含んでいれば、遅延配列に値を入れた後に評価
if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd) {
mLazyArr[pCurrNode] = pUpdateVal;
LazyEval(pCurrNode);
return;
}
// そうでなければ、2つの区間に再帰呼出し
int ChildNode1 = DeriveChildNode(pCurrNode);
int ChildNode2 = ChildNode1 + 1;
RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, ChildNode1);
RangeUpdate(pSearchStaInd, pSearchEndInd, pUpdateVal, ChildNode2);
// カレントノードの更新
mTreeNodeArr[pCurrNode] = Math.Min(mTreeNodeArr[ChildNode1], mTreeNodeArr[ChildNode2]);
}
// 開始添字と終了添字とカレントノードを引数として、最小値を返す
internal int Query(int pSearchStaInd, int pSearchEndInd, int pCurrNode)
{
// 該当ノードを遅延評価する
LazyEval(pCurrNode);
int CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;
int CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;
// OverLapしてなければ、int.MaxValue
if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd)
return int.MaxValue;
// 完全に含んでいれば、このノードの値
if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd)
return mTreeNodeArr[pCurrNode];
// そうでなければ、2つの子の最小値
int ChildNode1 = DeriveChildNode(pCurrNode);
int ChildNode2 = ChildNode1 + 1;
int ChildVal1 = Query(pSearchStaInd, pSearchEndInd, ChildNode1);
int ChildVal2 = Query(pSearchStaInd, pSearchEndInd, ChildNode2);
return Math.Min(ChildVal1, ChildVal2);
}
internal void DebugPrint()
{
for (int I = 0; I <= UB; I++) {
if (mLazyArr[I].HasValue) {
Console.WriteLine("mTreeNodeArr[{0}] = {1} , mLazyArr[{0}] = {2}",
I, mTreeNodeArr[I], mLazyArr[I]);
}
else {
Console.WriteLine("mTreeNodeArr[{0}] = {1}", I, mTreeNodeArr[I]);
}
}
}
}
#endregion