Problem type : Batch
Time limit : 2.0 second(s)
Memory limit : 64 megabyte(s)
การแข่งขันยิงธนูได้ถูกจัดขึ้นตามหลักเกณฑ์ต่าง ๆ ดังนี้ มีเป้ายิงทั้งหมด N เป้าถูกจัดเรียงในแนวเส้นตรงและมีหมายเลขตั้งแต่ 1 ถึง N ตามตำแหน่งของพวกมันบนแนวเส้นตรงนั้น (เป้ายิงทางซ้ายมือสุดจะเป็นเป้ายิงหมายเลขที่ 1 และเป้ายิงทางขวามือสุดจะเป็นเป้ายิงหมายเลขที่ N) นอกจากนี้ ยังมีผู้ยิงธนูทั้งหมด 2N คน ในระหว่างการแข่งขัน จะมีผู้ยิงธนู 2 คนต่อ 1 เป้ายิงทุกครั้งและในทุกรอบการแข่งขันจะดำเนินไปตามขั้นตอนต่าง ๆ ดังนี้
ผู้ยิงธนูทั้ง 2 คนในแต่ละเป้ายิงจะแข่งขันกันเพื่อหาผู้ชนะและผู้แพ้ในระหว่างพวกเขา จากนั้น ผู้ยิงธนูทุกคนจะเรียงตัวกันใหม่ ดังนี้
- ผู้ชนะที่เป้ายิงตั้งแต่หมายเลขที่ 2 ถึงหมายเลขที่ N ให้เคลื่อนที่ไปยังเป้ายิงที่อยู่ทางซ้ายมือของพวกเขา (ยกตัวอย่าง เช่น เป้ายิงหมายเลขที่ 1 ถึง N-1 ตามลำดับ)
- ผู้แพ้ที่เป้ายิงตั้งแต่หมายเลขที่ 2 ถึงหมายเลขที่ N และผู้ชนะที่เป้ายิงหมายเลขที่ 1 ให้ยืนอยู่ที่เป้ายิงเดิม
- ผู้แพ้ที่เป้ายิงหมายเลขที่ 1 ให้เคลื่อนที่ไปยังเป้ายิงหมายเลขที่ N
การแข่งขันนี้จะดำเนินไปทั้งหมด R รอบการแข่งขัน โดยจำนวนที่น้อยที่สุดของรอบการแข่งขันจะมากกว่าหรือเท่ากับจำนวนผู้ยิงธนู (ยกตัวอย่าง เช่น R ≥ 2N)
คุณคือผู้ยิงธนูคนเดียวเท่านั้นที่มาถึงการแข่งขันตรงเวลา ส่วนผู้ยิงธนูอีก 2N - 1 คนได้มาถึงก่อนหน้านี้และได้ยืนเรียงแถวกันในแนวเส้นตรงเรียบร้อยแล้ว สิ่งที่คุณต้องทำตอนนี้คือแทรกตัวเองเข้าไปที่จุด ๆ หนึ่งในแถวของพวกเขา และหลังจากที่คุณเข้าประจำที่เรียบร้อยแล้ว ผู้ยิงธนูที่อยู่ตำแหน่งทางซ้ายมือสุดทั้ง 2 คนในแถวจะเริ่มการแข่งขันในเป้ายิงหมายเลขที่ 1 แล้วผู้ยิงธนูที่อยู่ถัดไปอีก 2 คนจะเริ่มแข่งขันกันในเป้ายิงหมายเลขที่ 2 และเป็นเช่นนี้เรื่อยไปจนกระทั่งผู้ยิงธนูที่อยู่ตำแหน่งขวามือสุดทั้ง 2 คนแข่งขันกันในเป้ายิงหมายเลขที่ N
ผู้ยิงธนูทั้งหมด 2N คนในการแข่งขัน (ซึ่งรวมทั้งตัวคุณเองด้วย) จะถูกจัดลำดับตามทักษะความสามารถ โดยผู้ที่มีลำดับที่ต่ำกว่าจะหมายถึงผู้ที่มีทักษะเหนือกว่า ไม่มีผู้ยิงธนู 2 คนใด ๆ ที่มีหมายเลขลำดับเดียวกัน นอกจากนี้ เมื่อใดก็ตามที่ผู้ยิงธนู 2 คนแข่งขันกัน ผู้ที่มีหมายเลขลำดับต่ำกว่าจะเป็นผู้ชนะเสมอ
เมื่อคุณรู้ทักษะความสามารถของผู้เข้าแข่งขันแต่ละคนแล้ว คุณก็อยากที่จะแทรกตัวคุณเองเข้าไปในตำแหน่งที่คุณจะแน่ใจได้ว่า คุณจะได้จบการแข่งขันในเป้ายิงหมายเลขที่น้อยที่สุดเท่าที่จะเป็นไปได้ และถ้ามีหนทางหลากหลายที่จะทำแบบนี้ได้ คุณจะชอบหนทางที่คุณจะได้เริ่มต้นการแข่งขันในเป้ายิงหมายเลขที่มากที่สุดที่จะเป็นไปได้มากกว่าหนทางอื่น
งานของคุณ
จงเขียนโปรแกรมเพื่อรับหมายเลขลำดับแสดงทักษะความสามารถของผู้ยิงธนูทุกคน รวมทั้งตัวคุณเองด้วย และค่าการเรียงแถวในแนวเส้นตรงของคู่แข่งของคุณ แล้วพิจารณาหาหมายเลขของเป้ายิงที่คุณจะใช้เริ่มต้นการแข่งขัน เพื่อให้บรรลุตามวัตถุประสงค์ของคุณตามที่ได้กล่าวถึงไว้ก่อนหน้านี้แล้ว
เงื่อนไข
1 ≤ N ≤ 200 000 คือ จำนวนของเป้ายิงซึ่งจะต้องเท่ากับครึ่งหนึ่งของจำนวนผู้เข้าแข่งขันยิงธนู
2N ≤ R ≤ 1 000 000 000 คือจำนวนรอบการแข่งขัน
1 ≤ Sk ≤ 2N คือ หมายเลขลำดับแสดงทักษะความสามารถของผู้ยิงธนูคนที่ k
ข้อมูลนำเข้า
โปรแกรมของคุณจะต้องอ่านข้อมูลจากคีย์บอร์ด (standard input) ดังนี้
ในบรรทัดแรก ประกอบด้วยเลขจำนวนเต็ม N และ R ซึ่งแยกกันด้วยช่องว่าง
แต่ละ 2N บรรทัดถัดมา ให้ลงรายการของหมายเลขลำดับแสดงทักษะความสามารถของผู้ยิงธนูแต่ละคน โดยในบรรทัดแรกจะเป็นหมายเลขลำดับทักษะของคุณ ส่วนบรรทัดอื่น ๆ ที่เหลือจะเป็นหมายเลขลำดับทักษะของผู้ยิงธนูที่เหลือ ผู้ยิงธนู 1 คนต่อ 1 บรรทัดตามลำดับที่พวกเขายืนเรียงแถวกันในแนวเส้นตรง (จากซ้ายไปขวา) ในแต่ละ 2N บรรทัดเหล่านี้จะประกอบด้วยเลขจำนวนเต็มเพียงค่าเดียวที่มีค่าตั้งแต่ 1 ถึง 2N โดยหมายเลขลำดับแสดงทักษะหมายเลขที่ 1 หมายถึงคนที่เก่งที่สุดและหมายเลขลำดับแสดงทักษะที่ 2N จะหมายถึงที่คนที่แย่ที่สุด และไม่มีผู้ยิงธนู 2 คนใด ๆ ที่มีหมายเลขลำดับเดียวกัน
ข้อมูลส่งออก
โปรแกรมของคุณจะต้องเขียนข้อมูลออกมาทางจอภาพ (standard output) ภายในบรรทัดเดียว ซี่งประกอบด้วยเลขจำนวนเต็มเพียงค่าเดียวที่มีค่าตั้งแต่ 1 ถึง N แสดงหมายเลขของเป้ายิงที่คุณจะใช้เริ่มต้นการแข่งขันการให้คะแนน
สำหรับการทดสอบ จะมีค่า 60 คะแนน เมื่อ N มีค่าไม่เกิน 5000
และสำหรับบางส่วนของการทดสอบเหล่านี้ จะมีค่า 20 คะแนน เมื่อ N มีค่าไม่เกิน 200
ที่มา: 21-st International Olympiad In Informatics– August 8 - 15, 2009 (Day 1)
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 4 8 7 4 2 6 5 8 1 3 | 3 |
| 4 9 2 1 5 8 3 4 7 6 | 2 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้