{
…‘…�…� ’“��ˆ� �Ž ˆ�”Ž�Œ€’ˆŠ€ ˜“Œ…�'02 - 16 ­®¥¬¢°¨ 2002
’…Œ€ ‡€ 9 – 10 Š‹€‘ (ƒ�“�€ B)

‡ ¤ ·  3.  —ˆ‘‹Ž�…„

� ¯¨¸¥²¥ ¯°®£° ¬  GRADE.EXE, ª®¿²® ¯® § ¤ ¤¥­  °¥¤¨¶  ®² ¶¥«¨ ¯®«®¦¨²¥«­¨
·¨±«  ­ ¬¨°  ² ª¨¢ , ª®«ª®²® ¬®¦¥ ¯®-¬ «ª® ­  ¡°®© ¨§¬¥¦¤³ ²¿µ, ª®¨²®,  ª®
¡º¤ ² ®²±²° ­¥­¨ ®² °¥¤¨¶ ² , ²¿ ¹¥ ±¥ ®ª ¦¥ ­¥ ­ ¬ «¿¢ ¹  (¢±¿ª® ·¨±«® ¢ ­¥¿
¹¥ ±¥ ¯°¥¤µ®¦¤  ± ¬® ®² ¯®-¬ «ª¨ ¨«¨ ° ¢­¨ ­  ­¥£®).

‚µ®¤­¨²¥ ¤ ­­¨ ±º¤º°¦ ² ¥¤¨­±²¢¥­ °¥¤, ¢ ª®©²® ±  § ¯¨± ­¨ ·¨±« ²  ®²
°¥¤¨¶ ² , ° §¤¥«¥­¨ ± ¨­²¥°¢ «¨.  ’¥ ±  ­¥ ¯®¢¥·¥ ®² 1 000 000 ­  ¡°®©, ª ²®
¢±¿ª® ®² ²¿µ ¥ ­¥ ¯®-£®«¿¬® ®² 30 000.

�¥§³«² ²º² ±º¤º°¦  ¥¤¨­ °¥¤ ± ¯®°¥¤­¨²¥ ­®¬¥°  ­  ­ ¬¥°¥­¨²¥ ·¨±« , ° §¤¥«¥­¨
± ¨­²¥°¢ «¨ (¡°®¥­¥²® § ¯®·¢  ®² 1). ‚µ®¤­¨²¥ ¤ ­­¨ ±  ² ª¨¢ , ·¥ ¢ ¨§µ®¤ 
¢¨­ £¨ ¹¥ ¨¬  ¯®­¥ ¥¤­® ·¨±«®.

‚µ®¤­¨²¥ ¤ ­­¨ ±¥ ·¥² ² ®² ±² ­¤ °²­¨¿ ¢µ®¤,   ¨§µ®¤­¨²¥ ¤ ­­¨ ±¥ § ¯¨±¢ ² ­ 
±² ­¤ °²­¨¿ ¨§µ®¤.

�°¨¬¥°.

‚µ®¤
3 1 2 0 5 4

ˆ§µ®¤
1 4 5

(‚º§¬®¦¥­ ®²£®¢®° ¥ ¨ 1 4 6)


�…˜…�ˆ…:

…¤­® ¢º§¬®¦­® °¥¸¥­¨¥ ­  § ¤ · ²  ¥ ¤  ±¥ £¥­¥°¨° ² ¢±¨·ª¨ ¢º§¬®¦­¨ ­¥
­ ¬ «¿¢ ¹¨ ¯®¤°¥¤¨¶¨ ­  ¢µ®¤­ ²  ¨ ®² ²¿µ ¤  ±¥ ¨§¡¥°¥ ­ ©-¤º«£ ²  (² ª  ¹¥
®²±²° ­¨¬ ¢º§¬®¦­® ­ ©-¬ «ª® ·¨±«  ®² °¥¤¨¶ ² ). ’®¢ , ®¡ ·¥, ¹¥ ®²­¥¬¥ ³¦ ±­®
¬­®£® ¢°¥¬¥ ¤®°¨ ¯°¨ ±° ¢­¨²¥«­® ¬ «ª  °¥¤¨¶ ,   ¬ ª±¨¬ «­¨¿² ¡°®© ·¨±«  ¢
°¥¤¨¶ ²  ¬®¦¥ ¤  ¥ ¤® 1 000 000.

‡ ²®¢  ²°¿¡¢  ¤  ¯®¬¨±«¨¬ §  ­¿ª ª¢® ¯®-¤®¡°¥ °¥¸¥­¨¥. …¤­  ¤®¡°  ¥ ¨¤¥¿ ¤ 
­ ¬¥°¨¬ ­ ©-¤º«£ ²  ¢º§¬®¦­  ¯®¤°¥¤¨¶ , § ¢º°¸¢ ¹ ²  ± ®¯°¥¤¥«¥­® ·¨±«® ­ 
°¥¤¨¶ ² . �°¨« £ ©ª¨ ¤¨°¥ª²­® ²¥µ­¨ª ²  ­  ¤¨­ ¬¨·­® ®¯²¨¬¨° ­¥ §  ² §¨ ¨¤¥¿,
¹¥ ¯®«³·¨¬:
 Seq[i] = max(1, Seq[j]+1 | §  ¢±¿ª® j: 1<=j<i ¨ num[j]<=num[i])
ªº¤¥²® num[i] ¥ i-²®²® ·¨±«® ®² °¥¤¨¶ ² ,   Seq[i] ¥ ¤º«¦¨­ ²  ­  ­ ©-¤º«£ ² 
¯®¤°¥¤¨¶  § ¢º°¸¢ ¹  ± i-²®²® ·¨±«®,   j-²®²® ·¨±«® ±  ¥¢¥­²³ «­¨²¥
¯°¥¤¯®±«¥¤­¨ ·¨±«  ¢ ²º°±¥­ ²  ¯®¤°¥¤¨¶ . ‡  ¯®-ª° ²ª® § ¯¨±¢ ­¥ ¹¥ ¨§¯®«§¢ ¬¥
<i,s> §  ¯®¤°¥¤¨¶  § ¢º°¸¢ ¹  ± i-²®²® ·¨±«®, ¨¬ ¹  ¤º«¦¨­  ° ¢­  ­  s
(­¿ª ª¢  ±²®©­®±²).
‡  ¤  ­ ¬¥°¨¬ ®²£®¢®°  ­  §  § ¤ · ²  ¹¥ ²°¿¡¢  ¤  ­ ¬¥°¨¬ <1,Seq[1]>,
<2,Seq[2]>, . . ., <N,Seq[N]> ¨ ®² ²¿µ ¤  ¨§¡¥°¥¬ ² §¨ <R,Seq[R]>, §  ª®¿²®
Seq[R] ¥ ­ ©-£®«¿¬®. ’®¢  ¬®¦¥ ¤  ±² ­¥ ¯® ±«¥¤­¨¿ ­ ·¨­:
Seq[1] := 1;
R := 1;
for i := 2 to N do begin
  Seq[i] := 1;
  for j := 1 to i-1 do
    if (Seq[j] >= Seq[i]) and (num[j] <= num[i])
      then Seq[i] := Seq[j]+1;
  if Seq[i] > Seq[R] then R := i;
end;
’ ª  °¥ «¨§¨° µ¬¥ £®°­ ²  ¨¤¥¿, ­® ²®¢  °¥¸¥­¨¥ ¨¬  ±«®¦­®±² Ž(N*N), ª®¥²® ¥
­¥§ ¤®¢®«¨²¥«­® ¯°¨ ®£° ­¨·¥­¨¿²  ¢ § ¤ · ² . „  ±¥ ®¯¨² ¬¥ ¤  ®¯²¨¬¨§¨° ¬¥
²®¢  °¥¸¥­¨¥.

�¥ª  ° §£«¥¤ ¬¥ ¢º§¬®¦­¨²¥ ±²®©­®±²¨ ­  <j,Seq[j]>, ª®£ ²® ­ ¬¨° ¬¥
<i,Seq[i]>. „  ¤®¯³±­¥¬ ·¥ ±º¹¥±²¢³¢ ² ¤¢¥ ° §«¨·­¨ ±²®©­®±²¨ ­  j – j1 ¨ j2
(².¥. 1<=j1<i, 1<=j2<i, j1<>j2), §  ª®¨²® ¥ ¨§¯º«­¥­® Seq[j1]=Seq[j2]=L. �¥§
®£° ­¨·¥­¨¿ ¬®¦¥¬ ¤  ¨§¡¥°¥¬ j1-²® ·¨±«® ®² °¥¤¨¶ ²  ¤  ¡º¤¥ ­¥ ¯®-£®«¿¬® ®²
j2-to (².¥. num[j1]<=num[j2]). ’®£ ¢ , ª®£ ²® ²º°±¨¬ ±²®©­®±²²  ­  Seq[i],
¬®¦¥¬ ¤  �… ° §£«¥¦¤ ¬¥ j=j2, § ¹®²®:
  €) ²¿ ¡¨ ­¨ ¤ «  <i,L+1>,  ª® ¥ ¨§¯º«­¥­® num[j2]<=num[i]. Ž¡ ·¥
num[j1]<=num[j2]; ±«¥¤®¢ ²¥«­® ²®£ ¢  num[j1]<=num[i] ².¥. §  j=j1 ±º¹® ¹¥
¯®«³·¨¬ <i,L+1>.
  �) €ª® ¯ºª ­¥ ¥ ¨§¯º«­¥­® num[j2]<=num[i], ²® j2-²® ·¨±«® ­¥ ¬®¦¥ ¤  ¡º¤¥
¯°¥¤¯®±«¥¤­® ¢ ¯®¤°¥¤¨¶  § ¢º°¸¢ ¹  ± i-²®²® ·¨±«®.
’®¢  ¡¨ ­¨ ¤ «® ­¿ª ª¢  ®¯²¨¬¨§ ¶¨¿ ±²¨£  ¤  ¬®¦¥¬ ¤  £® ¨§¯®«§¢ ¬¥ ¤®¡°¥. „ 
¯° ¢¨¬ ­¿ª ª¢  ¯°®¢¥°ª  §  ±²®©­®±²¨²¥, ª®¨²® ¯°¨¥¬  j ¢ ¶¨ªº«  “for j := 1 to
i-1 . . .” ¡¨ ¡¨«® ²°³¤­®.
„  ° §£«¥¤ ¬¥ ¯®-¢­¨¬ ²¥«­® j1 ¨ j2 ®² £®°­¨¿ ¯°¨¬¥°. ‡  ²¿µ ¥ ¢¿°­®
Seq[j1]=Seq[j2]=L ¨ num[j1]<=num[j2]. ‘«¥¤®¢ ²¥«­® §  ¢±¿ª® j ¢ ¨­²¥°¢ « 
[1,i-1], §  ª®¥²® ¥ ¢¿°­® Seq[j]=L ­¨ ¨­²¥°¥±³¢  ± ¬® ²®¢  j, §  ª®¥²® num[j]
¥ ¬¨­¨¬ «­®. …²® § ¹®, ¥ «®£¨·­® ¤  ¯®¤¤º°¦ ¬¥ ¬ ±¨¢ Last, ª®©²® §  ¢±¿ª®
¢º§¬®¦­  ¤® ¬®¬¥­²  ¤º«¦¨­  X, ¯®¬­¨ ¨­¤¥ª±  j ­  ­ ©-¬ «ª®²® ·¨±«® ®²
°¥¤¨¶ ² , §  ª®¥²® ¥ ¢¿°­® Seq[j]=X, ².¥. Last[X] ¥ ¨­¤¥ª±  ­  ­ ©-¬ «ª®²®
·¨±«® ®² ¢±¨·ª¨ ¯®±«¥¤­¨ ·¨±«  ­  ¯®¤°¥¤¨¶¨ ± ¤º«¦¨­  X. „  ¢¨¤¨¬ ª ª ²®§¨
¬ ±¨¢ ¬®¦¥ ¤  ­¨ ¯®¬®£­¥ §  ­ ¬¨° ­¥²® ­  Seq[i].

�¥ª  ¯º°¢® ¨§ª ¦¥¬ ²¢º°¤¥­¨¥²®, ·¥ Num[Last[p]]<=Num[Last[q]], ¯°¨ p<q, ².¥.
 ª® ®² ¢±¨·ª¨ ¢º§¬®¦­¨ ­ ©-¤º«£¨ ¯®¤°¥¤¨¶¨, ¨¬ ¹¨ ¤º«¦¨­  p, ¨§¡¥°¥¬ ² §¨
§ ¢º°¸¢ ¹  ± ­ ©-¬ «ª®²® ·¨±«® (·¨±«®²® ¹¥ ¥ Num[Last[p]]), ­¥ª  ²¿ ¥ PSeq, ¨
 ª® ®² ¢±¨·ª¨ ¢º§¬®¦­¨ ­ ©-¤º«£¨ ¯®¤°¥¤¨¶¨, ¨¬ ¹¨ ¤º«¦¨­  q, ªº¤¥²® q ¥
¯®-£®«¿¬® ®² p, ¨§¡¥°¥¬ ² §¨ § ¢º°¸¢ ¹  ± ­ ©-¬ «ª® ·¨±«®(·¨±«®²® ¹¥ ¥
Num[Last[q]]), ­¥ª  ²¿ ¥ QSeq, ²® ¯®±«¥¤­®²® ·¨±«® ­  PSeq ¹¥ ¥ ­¥ ¯®-£®«¿¬®
®² ¯®±«¥¤­®²® ·¨±«® ­  QSeq. „®¯³±ª ­¥²® ­  ¯°®²¨¢­®²® ¢®¤¨ ¤® ¯°®²¨¢®°¥·¨¥ ±
¤¥´¨­¨¶¨¿²  ­  Last[p], § ¹®²® ±«¥¤ ª ²® “¨§²°¨¥¬” ¯®±«¥¤­¨²¥ q-p ·¨±«  ®²
QSeq, ¹¥ ¯®«³·¨¬ ¯®¤°¥¤¨¶  ± ¤º«¦¨­  p, ¨¬ ¹  ¯®±«¥¤­® ·¨±«® ­¥ ¯®-£®«¿¬® ®²
Num[Last[q]] (QSeq ¥ ­¥ ­ ¬ «¿¢ ¹ ), ­® Num[Last[p]]>Num[Last[q]];
±«¥¤®¢ ²¥«­® Last[p] ­¥ ®²£®¢ °¿ ­  ¤¥´¨­¨¶¨¿²  ±¨ ¨ ¤®¯³±ª ­¥²® ¥ ­¥ ¢¿°­®.

€ ±¥£  ¤  ¢¨¤¨¬ ª ª ¹¥ ­ ¬¥°¨¬ Seq[i]. �¥ª  Longest=max(Seq[j]) §  1<=j<i,
².¥. Longest ¥ ¤º«¦¨­ ²  ­  ­ -¤º«£ ²  ¯®¤°¥¤¨¶  ¤® ¬®¬¥­² .
1±«.) Num[i]<Num[Last[1]] ².¥. i-²®²® ·¨±«® ¥ ¯®-¬ «ª® ®² ¢±¨·ª¨ ·¨±«  ¤®
¬®¬¥­²  (¢±¨·ª¨ ¯®¤°¥¤¨¶¨ ± ¤º«¦¨­  1). ‘¯®°¥¤ ¤¥´¨­¨¶¨¿²  ­  Last ±«¥¤¢ , ·¥
Last[1]:=i;. ’º© ª ²®, i-²®²® ·¨±«® ¥ ­ ©-¬ «ª®²® ¤® ¬®¬¥­² , ²® ­¥ ¬®¦¥ ¤ 
¡º¤¥ ¯®±«¥¤¥­ ­  ¥«¥¬¥­² ­  ¯®¤°¥¤¨¶¨ ± ¤º«¦¨­  2 ¨«¨ ¯®-¤º«£¨, ².¥.
Seq[i]:=1;.
2±«.) Num[i]>=Num[Last[Longest]] ².¥. i-²®²® ·¨±«® ¥ ¯®-£®«¿¬® ¨«¨ ° ¢­® ­ 
¯®±«¥¤­®²® ·¨±«® ­  ­ ©-¤º«£ ²  ¯®¤°¥¤¨¶  ¤® ¬®¬¥­² . ‘«¥¤®¢ ²¥«­®
Seq[i]=Longest+1. € ®²²³ª, Longest:=Longest+1; Last[Longest]:=i;
3±«.) Š®£ ²® ­¥ ±  ¨§¯º«­¥­¨¥ ³±«®¢¨¿²  ®² ±«.1 ¨ 2, ²º°±¨¬ ²®¢  j, §  ª®¥²® ¥
¨§¯º«­¥­®:
   *) Num[i] < Num[Last[j]] ¨
   *) Num[i] >= Num[Last[j-1]]
’®ª®¢  j ±º¹¥±²¢³¢  ¯®° ¤¨ ¤¢  ´ ª² :
   I) Num[i] ¥ ¢ ¨­²¥°¢ «  [ Num[Last[1]], Num[Last[Longest]] ) – ¨­²¥°¢ «º² ¥
§ ²¢®°¥­ ®²«¿¢® ¨ ®²¢®°¥­ ¢¤¿±­® - ¢¿°­® ®² ²®¢  ·¥ ±¬¥ ±²¨£­ «¨ ¤® ±«.3,   ­¥
±«.1 ¨«¨ ±«.2.
  II) Num[Last[p]]<=Num[Last[q]], ¯°¨ p<q.
� ¬¨° ­¥²® ­  j ±² ¢  ± ¤¢®¨·­® ²º°±¥­¥, ª®¥²® ±² ¢  ± log ¤¢®¨·¥­ ®² Longest
­  ¡°®© ±²º¯ª¨ (±«®¦­®±² O(log Longest)). Ž²²³ª, Seq[i]:=j; Last[j]:=i;,
§ ¹®²® ­¿¬  ­ ·¨­ Seq[i]>j, ¯®­¥¦¥ ²®¢  ®§­ · ¢ , ·¥ ¨¬  ¯®¤°¥¤¨¶  ¤® ¬®¬¥­² ,
± ¤º«¦¨­  ¯®­¥ j, ª®¿²® § ¢º°¸¢  ± ·¨±«® ­¥ ¥ ¯®-£®«¿¬® ®² i-²®²®; ­® ®²
±²®©­®±²¨²¥ ­  ¬ ±¨¢  Last ±¥ ¢¨¦¤ , ·¥ ­¿¬  ² ª ¢ ;   ¯ºª ¨¬  ¯®¤°¥¤¨¶  ±
¤º«¦¨­  j-1, § ¢º°¸¢ ¹  ± ·¨±«® ª®¥²® ­¥ ¥ ¯®-£®«¿¬® ®² i-²®²® ¨ § ²®¢ 
Seq[i]=j.

‘²°®¥©ª¨ ¬ ±¨¢  ¯® £®°¥®¯¨± ­¨¿ ­ ·¨­ «¥±­® ¬®¦¥ ¤  ±¥ ¤®ª ¦¥ ¯® ¨­¤³ª¶¨¿, ·¥
¢±¥ª¨ ­¥£®¢ ¥«¥¬¥­² ± ¨­¤¥ª± ¢ ¨­²¥°¢ «  [1,Longest] ¨¬  ±²®©­®±² ¯°¨ i>2.

ˆ ² ª  se ±²¨£  ¤® ¯°®£° ¬ ²  ¯®-¤®«³, §  ª®¿²® ¹¥ ®²¡¥«¥¦¨¬ ·¥ ­¥ ­¨ ¥ ­³¦¥­
¬ ±¨¢  Seq! �³¦­¨ ±  ­¨ ± ¬® ¬ ±¨¢  Num (±º¤º°¦ ¹ ·¨±« ²  ­  ­ · « ²  °¥¤¨¶ ),
¬ ±¨¢  Last (®¯¨± ­ ¯®-£®°¥) ¨ ¥¤¨­ ¬ ±¨¢ Prev, ª®©²® ±º¤º°¦  ·¨±«®²® ¯°¥¤¨
i-²®²® ¢ <i,Seq[i]> (¯°¥¤¯®±«¥¤­®²® ·¨±«® ¢ ­ ©-¤º«£ ²  ¯®¤°¥¤¨¶ , § ¢º°¸¢ ¹ 
± i-²®²® ·¨±«®). ‘º¹® ² ª  ¨§¯®«§¢ ¬ ¥¤¨­ ¯®¬®¹¥­ ¬ ±¨¢ Remove, §  ¤  ¬ °ª¨° ¬
ª®¨ ¥«¥¬¥­²¨ ²°¿¡¢  ¤  ¡º¤ ² ¬ µ­ ²¨ ®² ­ · « ²  °¥¤¨¶ , §  ¤  ±¥ ¯®«³·¨
¬ ª±¨¬ «­® ¤º«£ , ­¥ ­ ¬ «¿¢ ¹  ¯®¤°¥¤¨¶ , ­® ¨§¯®«§¢ ­¥²® ­  ²®§¨ ¬ ±¨¢ ¬®¦¥
¤  ±¥ ¨§¡¥£­¥.

‘«®¦­®±²²  ­  ²®¢  °¥¸¥­¨¥ ¥ O(N*logR), ªº¤¥²® R ¥ £®«¥¬¨­ ²  ­  ­ ©-¤º«£ ² 
­¥ ­ ¬ «¿¢ ¹  °¥¤¨¶ ; ­® R ¬®¦¥ ¤  ¥ ° ¢­® ­  N, ².¥. °¥¸¥­¨¥²® ¨¬  ±«®¦­®±²
O(N*logN) ¢ ­ ©-«®¸¨¿ ±«³· ©.

Kristiyan Haralambiev
}

program Chislored;
const
        InFile                  = ''; // when the name of a file is ''
        OutFile                 = ''; // the standard i/o is used
        Max                     = 1000*1000;
var
        N, Longest              : LongInt;
        Num                     : array[1..Max] of LongInt;
        Last, Prev              : array[1..Max] of LongInt;
        Remove                  : array[1..Max] of Boolean;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure InPut;
var
        F                       : Text;
begin
  Assign(F, InFile); ReSet(F);

  N := 0;
  repeat
    Inc(N);
    Read(F, Num[N]);
  until Eoln(F) or Eof(F);

  Close(F);
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure Solve;
var
        I, J, K, Mid            : LongInt;
begin
  FillChar(Prev, SizeOf(Prev), 0);

  Longest := 1;
  Last[1] := 1;

  for K := 2 to N do begin
    if Num[K] < Num[ Last[1] ] then Last[1] := K // case 1
    else if Num[K] >= Num[ Last[Longest] ] then begin // case 2
      Inc(Longest);
      Last[Longest] := K;
      Prev[K] := Last[Longest-1];
    end
    else begin // case 3
     //binary search
      I := 1;
      J := Longest;
      while J - I > 1 do begin
        Mid := (I + J) div 2;
        if Num[ Last[Mid] ] > Num[K] then J := Mid else I := Mid;
      end;
     //update - it is true that I = J-1
      Last[J] := K;
      Prev[K] := Last[I];
    end;
  end; //end of for K := ...
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure OutPut;
var
        K                       : LongInt;
        F                       : Text;
begin
  Assign(F, OutFile); ReWrite(F);
  FillChar(Remove, SizeOf(Remove), True);

  K := Last[Longest];
  repeat
    Remove[K] := False;
    K := Prev[K];
  until K = 0;

  for K := 1 to N do
    if Remove[K] then Write(F, K, ' ');
  WriteLn(F);

  Close(F);
end;

{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
begin
  InPut;
  Solve;
  OutPut;
end.