Sachverhalt:
A.
Die in der Landwirtschaftszone und der kantonalen Landschaftsschutzzone gelegene Parzelle Nr. 1536 in Urnäsch ist mit dem Gasthaus "Rossfall" (nachstehend: Gasthaus) überbaut, in dem während zwei Jahrhunderten als Teil der Appenzeller Alpfahrt Sennenbälle durchgeführt wurden. Der nördliche Saaltrakt wurde im 1981 durch eine Gasexplosion stark beschädigt und in den Jahren 1985/86 mit finanzieller Unterstützung des Bundes, des Kantons Appenzell A.Rh. und der Gemeinde Urnäsch wieder aufgebaut. Der Südtrakt mit Gaststube, Wohnung und Terrasse weist gegen Westen und Osten herkömmliche Holztäferfassaden auf. Seine Südfassade war mit einem Holzschindelschirm bedeckt.
Das Gasthaus wurde 1991 mit Zustimmung des Gemeinderats Urnäsch als "Kulturobjekt ausserhalb der Bauzone Nr. 1.9" in den kantonalen Schutzzonenplan aufgenommen. Dieser Plan lag vom 3. Juni bis zum 2. Juli 1991 öffentlich auf und wurde in der Folge rechtskräftig.
Im Jahr 2001 wurde das Gasthaus von A._ und B._ (nachstehend: Bauherren) erworben. Diese liessen gestützt auf eine Baubewilligung vom 1. September 2003 an den Fassaden des nördlichen Saaltrakts die Holzschindeln gegen Westen und Norden durch Eternitschindeln ersetzen.
B.
Am 11. Januar 2006 stellten die Bauherren das Gesuch, die Sanierung der Südfassade des Gasthauses durch das Anbringen von Eternitschindeln zu bewilligen. Die Baubewilligungskommission Urnäsch bewilligte mit Entscheid vom 21. März 2006 die Sanierung der Südfassade mit der Auflage, dass anstelle der vorgesehenen Eternitschindeln Schindeln aus Holz anzubringen seien, wie dies das Planungsamt in seiner Bewilligung vom 17. März 2006 verlangt hatte. Gegen diese Auflage rekurrierten die Bauherren an das DBU. Dieses stellte am Augenschein vom 6. Juni 2006 fest, dass entgegen der strittigen Auflage die Holzschindeln an der Südfassade durch Eternitschindeln ersetzt worden waren. Mit Entscheid vom 15. August 2006 wies das DBU den Rekurs der Bauherren ab und ordnete zugleich an, dass diese innert drei Monaten ab Rechtskraft des Entscheids an der Südfassade des Gasthauses die Eternitschindeln durch Holzschindeln zu ersetzen hätten. Die dagegen von den Bauherren ergriffenen Rechtsmittel wiesen das Verwaltungsgericht am 27. Juni 2007 und das Bundesgericht am 11. Dezember 2008 ab, soweit darauf eingetreten wurde.
Am 16. März 2009 stellten die Bauherren beim DBU das Gesuch, im kantonalen Schutzzonenplan das Gasthaus als Kulturobjekt Nr. 1.9 zu streichen. Der Gemeinderat Urnäsch unterstützte dieses Gesuch.
Zudem ersuchten die Bauherren das Planungsamt darum, bis zum Entscheid über das Gesuch um Schutzentlassung den Vollzug der am 15. August 2006 verfügten Wiederherstellung des rechtmässigen Zustands aufzuschieben, was das Planungsamt am 3. April 2009 tat.
Das DBU wies am 7. Juni 2010 das Gesuch um Schutzentlassung des Gasthauses ab. Einen dagegen von den Bauherren erhobenen Rekurs wies der Regierungsrat mit Entscheid vom 18. Dezember 2012 ab. Diesen Entscheid fochten die Bauherren mit Beschwerde beim Obergericht des Kantons Appenzell A.Rh. an. Während des obergerichtlichen Verfahrens verkauften die Bauherren das Gasthaus an die C._ AG, welche die Bauherren ermächtigte, das Rechtsmittelverfahren bezüglich der Schutzentlassung in eigener Verantwortlichkeit weiterzuführen. Das Obergericht wies mit Urteil vom 27. Oktober 2016 die Beschwerde der Bauherren ab.
C.
Die Bauherren (Beschwerdeführer) erhoben Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, das Urteil des Obergerichts vom 27. Oktober 2016 aufzuheben und dem Gesuch vom 16. März 2009 um Entlassung des Gasthauses als Kulturobjekt Nr. 1.9 aus dem kantonalen Schutzzonenplan stattzugeben. Eventuell sei die Angelegenheit zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Mit Präsidialverfügung vom 3. Juli 2017 wies das Bundesgericht das Gesuch der Beschwerdeführer, der Beschwerde die aufschiebende Wirkung zuzuerkennen, ab.
Das Obergericht verzichtet auf Gegenbemerkungen zur Beschwerde. Das Departement Bau und Volkswirtschaft und der Regierungsrat des Kantons Appenzell A.Rh. beantragen, die Beschwerde abzuweisen. Das Bundesamt für Raumentwicklung (ARE) verzichtete auf eine Stellungnahme.

Erwägungen:
1.
1.1. Gegen das kantonal letztinstanzliche Urteil des Obergerichts, das eine Inventarentlassung und damit eine öffentlich-rechtliche Angelegenheit betrifft, steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (<ref-law>; vgl. Urteil 1C_593/2015 vom 25. Mai 2016 E. 1).
1.2. Das Bundesgerichtsgesetz enthält keine Vorschriften zum Parteiwechsel, weshalb nach <ref-law> die Bestimmungen des Bundeszivilprozesses (BZP; SR 273) sinngemäss anwendbar sind. Nach <ref-law> bleibt die Veräusserung der im Streite liegenden Sache während der Rechtshängigkeit ohne Einfluss auf die Legitimation zur Sache. Die Partei, welche den Streitgegenstand veräussert hat, ist daher auch vor Bundesgericht legitimiert, das Verfahren in ihrem Namen in Prozessstandschaft für fremdes Recht fortzuführen, wenn kein Parteiwechsel beantragt wurde (Urteile 1C_32/2007 vom 18. Oktober 2007 E. 1.1; 1C_142/2014 vom 13. März 2015 E. 2.4; je mit Hinweisen). Die Beschwerdeführer sind somit beschwerdelegitimiert, obwohl sie das Gasthaus bereits während des vorinstanzlichen Verfahrens veräussert haben.
1.3. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist die Beschwerde grundsätzlich einzutreten.
1.4. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann geltend gemacht werden, der angefochtene Entscheid verletze Bundesrecht, Völkerrecht oder kantonale verfassungsmässige Rechte (Art. 95 lit. a, b und c BGG). Die Verletzung des übrigen kantonalen Rechts kann abgesehen von hier nicht relevanten Ausnahmen gemäss <ref-law> vor Bundesgericht nicht gerügt werden; zulässig ist jedoch die Rüge, die Anwendung dieses Rechts führe zu einer Verletzung von Bundesrecht, namentlich des verfassungsmässigen Willkürverbots (<ref-ruling> E. 2 S. 149 f.). Nach der Praxis des Bundesgerichts verstösst ein Entscheid gegen dieses Verbot, wenn er im Ergebnis offensichtlich unhaltbar ist, weil er zum Beispiel eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt. Dass eine andere Lösung ebenfalls als vertretbar erscheint, genügt nicht (<ref-ruling> E. 2.2 S. 72 mit Hinweisen).
2.
2.1. Art. 86 des Gesetzes über die Raumplanung und das Baurecht des Kantons Appenzell A.Rh. vom 12. Mai 2003 (Baugesetz, BauG) lautet:
1 Als Naturobjekte sind ökologisch oder naturgeschichtlich bedeutsame Baumgruppen, Hecken, markante Einzelbäume, Teiche, Wasserfälle, Findlinge und Einzelgeotope und dergleichen zu bezeichnen.
2 Als Kulturobjekte sind Kulturdenkmäler sowie andere historisch oder künstlerisch wertvolle Einzelbauten, Baugruppen und Bauteile sowie Anlagen wie Wege, Trockensteinmauern und dergleichen zu bezeichnen.
3 Die geschützten Natur- und Kulturobjekte sind in ihrem Charakter und in ihrer schutzwürdigen Substanz langfristig zu erhalten. Die Grundeigentümerinnen und Grundeigentümer sind verpflichtet, sie dem Schutzzweck entsprechend zu pflegen und zu unterhalten.
4 Die Schutzwürdigkeit der Natur- und Kulturobjekte ist durch die verfügende Behörde zu überprüfen, sofern sich die Verhältnisse erheblich geändert haben. Die Eigentümerinnen und Eigentümer können von sich aus eine Überprüfung beantragen.
5 Bauten und Anlagen sind so zu gestalten, dass sie geschützte Natur- und Kulturobjekte nicht beeinträchtigen und in ihrer optischen Wirkung dem Schutzziel nicht widersprechen.
2.2. Die Vorinstanz erwog, der Natur- und Heimatschutz falle nach <ref-law> in die Regelungskompetenz der Kantone. Art. 30 Abs. 1 der Verfassung des Kantons Appenzell A.Rh. vom 30. April 1995 (KV) auferlege dem Kanton und den Gemeinden die Pflicht zur Ergreifung von Massnahmen zur Erhaltung und Pflege schützenswerter Landschafts- und Ortsbilder, Kulturgüter und Naturdenkmäler. Die entsprechenden Massnahmen würden in den Art. 79 ff. BauG geregelt. Diese Regelung verstosse nicht gegen übergeordnetes Recht, weil der Schutz von Kulturgütern namentlich gemäss Art. 30 Abs. 1 KV Sache der Kantone sei. Daran ändere nichts, dass das Baugesetz im Ingress als Grundlage Art. 31 KV und nicht Art. 30 KV nenne. Gemäss Art. 89 Abs. 2 BauG und Art. 79 Abs. 1 lit. d und h BauG könnten schützenswerte Objekte nicht nur klassische Kulturdenkmäler, sondern auch andere historisch, d.h. geschichtlich bzw. heimatkundlich wertvolle Einzelbauten sein. Es sei dabei etwa auf § 2 Abs. 1 des Denkmalschutzgesetzes des Kantons Zug zu verweisen. Das Gasthaus "Rossfall" sei ein historisch wertvoller Bau, weil es gemäss dem überzeugenden Gutachten der Eidgenössischen Kommission für Denkmalpflege (EKD) vom 18. Dezember 2015 ein einzigartiger Zeuge der tief verwurzelten, ortsgebundenen regionalen Tradition der Alpfahrt und des Sennenballs sei. Art. 86 BauG stelle daher für die Unterschutzstellung des Gasthauses eine hinreichende gesetzliche Grundlage dar.
2.3. Die Beschwerdeführer rügen, die Vorinstanz habe gegen das Willkürverbot (<ref-law>) und die Eigentumsgarantie (<ref-law>) verstossen, wenn sie Art. 86 BauG als gesetzliche Grundlage für den Schutz von Einzelbauten mit bloss heimat- oder volkskundlicher Bedeutung qualifiziert habe. Das Gasthaus habe aufgrund der im Saal durchgeführten Sennenbälle zwar eine solche Bedeutung. Dem Äusseren des Gasthauses komme hingegen keine besondere gestalterische oder bauhistorische Qualität zu, weil derartige Bauten im Appenzellerland zu Hunderten bestünden. Für seinen Schutz bestehe daher keine gesetzliche Grundlage, da Art. 86 BauG und auch Art. 79 Abs. 1 lit. h BauG keine Objekte mit nur heimat- oder volkskundlicher Bedeutung erwähnten. Der vorinstanzliche Hinweis auf das Denkmalschutzgesetz des Kantons Zug gehe fehl, weil im Kanton Appenzell A.Rh. ein solches Gesetz fehle. Diese Lücke könne nicht durch das Baugesetz geschlossen werden, weil es als Grundlage Art. 30 KV betreffend die Denkmalpflege nicht nenne und es daher zur Regelung der Denkmalpflege nicht geschaffen worden sei. Die entsprechenden Schutzbedürfnisse dürften daher bei der Auslegung des Baugesetzes nicht einbezogen werden. Demnach könnten gemäss der gesetzlichen Zielvorstellung von Art. 86 BauG nur bauhistorisch und nicht bloss volkskundlich wertvolle Objekte schützenswert sein. Eine Baute, die historische Bedeutung habe, weil darin einmal geschichtlich relevante Tätigkeiten stattgefunden hätten, sei daher nicht schützenswert. So sei gemäss der Rechtsprechung das "Café Odéon" nur schützenswert, weil sein Äusseres eine ablesbare Fortsetzung der inneren, zu schützenden Nutzung darstelle. Dies treffe beim vorliegenden Gasthaus nicht zu. Entsprechend habe der Regierungsrat in seinem Entscheid vom 11. Februar 1986 zur Begründung der Beiträge für den Wiederaufbau des Saalbaus ausgeführt, da kein eigentliches Baudenkmal vorliege und es um die Weiterführung einer stark verwurzelten bäuerlichen Tradition am ursprünglichen Ort gehe, falle der Wiederaufbau nicht in erster Linie in den Aufgabenbereich der Denkmal-, sondern der Kulturpflege und des Heimatschutzes.
2.4. Mit diesen Ausführungen legen die Beschwerdeführer nicht substanziiert dar, weshalb die im Ingress des Baugesetzes genannten Angaben über die Grundlagen dieses Gesetzes zwingend als abschliessend verstanden werden müssen. Dies ist auch nicht ersichtlich, weil das Baugesetz in den Art. 79 ff. Bestimmungen betreffend den Natur-, Landschafts-, Kulturobjekt- und Ortsbildschutz enthält. Daraus kann willkürfrei geschlossen werden, im Kanton Appenzell A.Rh. werde der Schutz von Kulturobjekten im Baugesetz geregelt, obwohl in seinem Ingress Art. 30 KV nicht als Grundlage erwähnt wird. Entscheidend ist, dass sich die interessierenden Bestimmungen des BauG auf eine Verfassungsnorm abstützen können. Demnach kann die Regelung des Schutzes von Kulturobjekten im Baugesetz in vertretbarer Weise gleich ausgelegt werden, wie eine entsprechende Regelung in einem Denkmalschutzgesetz. Die Vorinstanz verstiess daher nicht gegen das Willkürverbot, wenn sie unter den in Art. 79 Abs. 1 lit. d und h und Art. 86 Abs. 2 BauG genannten "historisch bzw. kulturgeschichtlich wertvollen Einzelbauten" auch geschichtlich bzw. heimatkundlich wertvolle Bauten subsumierte, zumal diese Auslegung mit dem aus dem Wortlaut abgeleiteten Sinn vereinbar ist. Dieser Sinn widerspricht auch nicht dem Regelungszweck, da gemäss der bundesgerichtlichen Rechtsprechung die Schutzwürdigkeit eines Objekts im Rahmen einer Gesamtbeurteilung zu ermitteln ist, bei der unter Berücksichtigung des kulturellen, geschichtlichen, künstlerischen und städtebaulichen Zusammenhangs geprüft wird, ob eine Baute als Zeuge und Ausdruck einer historischen, gesellschaftlichen, wirtschaftlichen und technischen Situation erhalten bleiben soll (vgl. <ref-ruling> E. 6.2 S. 182; Urteil 1C_543/2009 vom 15. März 2010 E. 2.3 mit Hinweisen). Da das Gasthaus ein einzigartiger Zeuge der Tradition des Sennenballs ist, durfte die Vorinstanz seine Schutzwürdigkeit auch dann in vertretbarer Weise bejahen, wenn seiner äusseren Erscheinung keine besondere bauhistorische Bedeutung zukommt. Die Vorinstanz verfiel auch nicht in Willkür, wenn sie nicht nur den Saaltrakt als schützenswert qualifizierte, da ein Bauwerk nach den praktizierten Grundsätzen der Denkmalpflege grundsätzlich als Ganzes zu betrachten ist (vgl. Urteil 1C_543/2009 vom 15. März 2010 E. 2.3 mit Hinweisen). Dies wird dadurch bestätigt, dass in vertretbarer Weise angenommen werden kann, die Tradition der Sennenbälle werde in der kollektiven Erinnerung mit dem Gasthaus als Ganzes in Verbindung gebracht. Unter diesen Umständen verstiess die Vorinstanz weder gegen das Willkürverbot noch gegen die Eigentumsgarantie, wenn sie Art. 86 BauG als gesetzliche Grundlage für die Unterschutzstellung des Gasthauses als Ganzes qualifizierte.
3.
3.1. Die Vorinstanz führte aus, gemäss Art. 86 Abs. 3 BauG müsse der Eigentümer den Charakter und die schutzwürdige Substanz des Schutzobjekts erhalten und es diesem Schutzzweck entsprechend pflegen und unterhalten. Diese Eigentumsbeschränkung müsse verhältnismässig sein, was von Amtes wegen zu prüfen sei. Die Beschwerdeführer hätten das bereits unter Schutz stehende Gasthaus gekauft und machten keine Umbau- oder Umnutzungspläne geltend, die mit den Erhaltungsverpflichtungen gemäss Art. 86 Abs. 3 BauG nicht vereinbar wären. Die bisherige Nutzung als Gasthaus sei weiterhin zulässig. Zudem dürften dem Schutzzweck nicht widersprechende bauliche Änderungen vorgenommen werden. Hingegen sei rechtskräftig entschieden worden, dass die an der Südfassade ohne Baubewilligung angebrachten Eternit- durch Holzschindeln zu ersetzen seien. Die entgegenstehenden Rentabilitätsüberlegungen fielen nicht ins Gewicht. Da das Gasthaus als Ganzes schutzwürdig sei, sei eine mildere Massnahme nicht ersichtlich. Demnach sei die Eintragung des Gasthauses als Schutzgegenstand (weiterhin) verhältnismässig.
3.2. Die Beschwerdeführer wenden ein, die heimat- und volkskundliche Bedeutung des Gasthauses im Zusammenhang mit dem Sennenball könne kein öffentliches Interesse am Erhalt der Fassaden begründen, weil dieser Ball unbehindert auch ohne den Schutz der Fassaden weitergeführt werden könne. Es sei daher unverhältnismässig, an der Auflage festzuhalten, an der Südfassade Holzschindeln anzubringen, zumal die Fassaden des Nordtrakts bereits mit einem (bewilligten) Eternitschirm eingekleidet seien.
3.3. Denkmalschutzmassnahmen müssen nach dem Grundsatz der Verhältnismässigkeit für das Erreichen des im öffentlichen Interesse liegenden Ziels geeignet, erforderlich und dem Betroffenen zumutbar sein. Ein durch Schutzmassnahmen verursachter Grundrechtseingriff ist namentlich dann unverhältnismässig, wenn eine ebenso geeignete mildere Anordnung für den angestrebten Erfolg ausreicht. Ob eine aus Gründen des Denkmalschutzes erfolgende Nutzungsbeschränkung das dem Eigentümer zumutbare Mass überschreitet, ist einzelfallweise aufgrund der gesamten Umstände zu beurteilen. Dabei sind Rentabilitätsüberlegungen umso geringer zu gewichten, je schutzwürdiger eine Baute ist (<ref-ruling> E. 2c S. 222). Zudem können rein finanzielle Interessen bei ausgewiesener Schutzwürdigkeit für sich genommen nicht ausschlaggebend sein (Urteil 1C_55/2011 vom 1. April 2011 E. 7.1 mit Hinweisen). Das Vorliegen eines öffentlichen Interesses und die Verhältnismässigkeit prüft das Bundesgericht bei der Beschränkung von Grundrechten frei (<ref-ruling> E. 4.4.1 S. 204 mit Hinweisen).
3.4. Gemäss der vorstehenden Erwägung darf das Gasthaus als Ganzes als Kulturdenkmal qualifiziert werden. Bei der Renovation von Baudenkmälern wird verlangt, dass die ursprünglichen Materialien verwendet werden, soweit sie als charakteristische Eigenschaften zum Zeugniswert des Objekts beitragen (Urteil 1C_578/2016 vom 28. Juni 2017 E. 4.6 mit Hinweis). Da der Südtrakt des Gasthauses - anders als sein wiederaufgebauter Nordtrakt - gegen Westen und Osten Holzfassaden herkömmlicher Bauart aufweist, kann beim Südtrakt die einheitliche Verkleidung der Fassaden mit Holz als charakteristische Eigenschaft qualifiziert werden (vgl. Urteil 1C_231/2008 vom 11. Dezember 2008 E. 3.2 und 3.3). Die Beschwerdeführer legen nicht dar, weshalb die Abdeckung der Südfassade mit Holzschindeln unzumutbar sein soll, was auch nicht ersichtlich ist. Dass Holzschindeln aufgrund ihrer beschränkten Lebensdauer periodisch ersetzt werden müssen, ist aufgrund der ausgewiesenen Schutzwürdigkeit des Gasthofs hinzunehmen (vgl. Urteil 1C_231/2008 vom 11. Dezember 2008 E. 3.2). Dies wird dadurch bestätigt, dass es im Appenzellerland gemäss den Angaben der Beschwerdeführer noch zahlreiche andere Häuser mit Holzfassaden gibt, die auch unterhalten werden müssen. Die Kosten für die Entfernung der Eternitschindeln sind unbeachtlich, da diese bösgläubig anbracht wurden und die Beschwerdeführer daher nach der Rechtsprechung in Kauf nehmen müssen, dass die Behörden namentlich zum Schutz der baulichen Ordnung dem Interesse an der Wiederherstellung des gesetzmässigen Zustands ein höheres Gewicht beimessen als ihren möglichen finanziellen Einbussen (<ref-ruling> E. 6.4 S. 39 f.). Wie die Vorinstanz sodann zutreffend darlegte, lässt die weitere Unterschutzstellung des Gasthauses sowohl seine bisherige Nutzung als auch bauliche Veränderungen zu, welche den Schutzzweck nicht tangieren (vgl. <ref-ruling> E. 6c S. 284 f.). Unter diesen Umständen erweist sich die Rüge der Verletzung des Verhältnismässigkeitsprinzips als unbegründet.
4. Nach dem Gesagten ist die Beschwerde abzuweisen. Bei diesem Ausgang des Verfahrens sind die Gerichtskosten den Beschwerdeführern aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- werden den Beschwerdeführern auferlegt.
3.
Dieses Urteil wird den Beschwerdeführern, dem Departement Bau und Volkswirtschaft, dem Regierungsrat und dem Obergericht des Kantons Appenzell Ausserrhoden, 4. Abteilung, sowie dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 27. Oktober 2017
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Merkli
Der Gerichtsschreiber: Gelzer