Q: Context: By 2010 BC, some of the earliest recorded farmers had settled in Beidha, a pre-pottery settlement just north of Petra. Petra is listed in Egyptian campaign accounts and the Amarna letters as Pel, Sela or Seir. Though the city was founded relatively late, a sanctuary has existed there since very ancient times. The Jewish historian, Josephus (ca. 37 -- 100), describes the region as inhabited by the Madianite nation as early as 1340 BC, and that the nation was governed by five kings, whom he names: "Rekem; the city which bears his name ranks highest in the land of the Arabs and to this day is called by the whole Arabian nation, after the name of its royal founder, Rekeme: called Petra by the Greeks." The famed architecture of Petra, and other Nabataean sites, was built during indigenous rule in early antiquity.

Question: when was the lost city of petra built?
Let's give stream of consciousness below
The relevant information to answer the above question is: The famed architecture of Petra, and other Nabataean sites, was built during indigenous rule in early antiquity. So the answer is during indigenous rule in early antiquity.